Exploring Metric Embeddings & Algorithms at METRIC 2011 in Paris 🗼

-------<br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)<br />-------<br />Workshop on Metric embeddings, algorithms  and hardness of approximation<br />January 17-21, 2011<br />-------<br />Jan 20, 10:30-11:30<br />Nisheeth Vishnoi (Bangalore)<br />On the Duality between Algorithms and Hardness in Approximability<br />-------<br />This talk will be concerned with how well can we approximate NP-hard problems.<br />One of the most successful algorithmic strategies, from an upper bound<br />perspective, is to write a tractable relaxation for an NP-hard problem and<br />present a "rounding" algorithm. To prove a hardness of approximation result,<br />on the other hand, one often gives a reduction assuming existence of<br />computationally hard structures, for instance those promised by the conjecture<br />P \neq NP.<br /><br />Until recently, these seemed to be two different facets of a problem. This<br />distinction is now blurring: we are beginning to understand systematic<br />recipes of how to use the output of algorithmic relaxations to come up with<br />reductions, and how to use the analysis of the hardness reduction to produce<br />a rounding algorithm for the relaxation itself.<br /><br />This viewpoint has led to the discovery of new and optimal algorithms and<br />reductions for several important problems such as Max-Cut, Vertex Cover and<br />beyond for which elegant and clever, but seemingly unrelated, algorithms and<br />reductions were previously known.