Mathieu Monday Jan 10 slides

IHPMathieuLecture2

Covered today in class:

– an exponential-size LP relaxation for Min-Cut with separation oracle, and proof that there is an integral optimum

– an exponential-size LP relaxation for Multiway cut with separation oracle, and a 3/2 approximation algorithm based on randomized rounding of the metric embedding into ell1.

– an exponential-size LP relaxation for Multicut with separation oracle, and an O(ln n) approximation algorithm based on carving balls from the metric embedding. Analysis partially deferred to Wednesday.

Wednesday and Friday’s lectures: after doing the end of the analysis, we will talk about SDP algorithms for: approximation quadratic programs, coloring a 3-colorable graph, correlation clustering, and unique games.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
Gallery | This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s