[metric 2011] Nisheeth Vishnoi

-------
METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)
-------
Workshop on Metric embeddings, algorithms  and hardness of approximation
January 17-21, 2011
-------
Jan 20, 10:30-11:30
Nisheeth Vishnoi (Bangalore)
On the Duality between Algorithms and Hardness in Approximability
-------
This talk will be concerned with how well can we approximate NP-hard problems.
One of the most successful algorithmic strategies, from an upper bound
perspective, is to write a tractable relaxation for an NP-hard problem and
present a "rounding" algorithm. To prove a hardness of approximation result,
on the other hand, one often gives a reduction assuming existence of
computationally hard structures, for instance those promised by the conjecture
P \neq NP.

Until recently, these seemed to be two different facets of a problem. This
distinction is now blurring: we are beginning to understand systematic
recipes of how to use the output of algorithmic relaxations to come up with
reductions, and how to use the analysis of the hardness reduction to produce
a rounding algorithm for the relaxation itself.

This viewpoint has led to the discovery of new and optimal algorithms and
reductions for several important problems such as Max-Cut, Vertex Cover and
beyond for which elegant and clever, but seemingly unrelated, algorithms and
reductions were previously known.