[Lecture 6:3/3] Using Randomness in Computer Science
Nicolas Schabanel
2011-02-04
Views 39
Lecture @ MPRI Paris Master of Computer Science (Université Paris Diderot) by Nicolas Schabanel
Feb 2, 2011 - 16:15-19:15 - Exhaustive Sampling
• A constant time (1+ε)-approximation for the size of a maximal matching in constant maximum degree graphs
• Exhaustive guessing 1: a polynomial time randomized (1+ε)-approximation (PTRAS) for Max-CUT in dense graphs
Feb 2, 2011 - 16:15-19:15 - Exhaustive Sampling
• A constant time (1+ε)-approximation for the size of a maximal matching in constant maximum degree graphs
• Exhaustive guessing 1: a polynomial time randomized (1+ε)-approximation (PTRAS) for Max-CUT in dense graphs
Report form
RELATED VIDEOS
