Approximating the optimum: Efficient algorithms and their limits

167 views · Published 6 September 2016 · 48:37 · Indexed 18 October 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

Most combinatorial optimization problems of interest are NP-hard to solve exactly.  To cope with this intractability, one settles for approximation algorithms with provable guarantee on the quality of  approximation.   Despite great success in designing approximation algorithms, underlying a vast majority of the work is the technique of linear programming, or more generally semi-definite programming. This poses the natural question:   How far can we push the technique of semi-definite programming?  Are there techniques that yield better approximations than semi-definite programming?    In this work, we show that the simplest semi-definite programs yield the best approximation for large classes of optimization problems ranging from constraint satisfaction problems (CSP) to graph labeling  problems, ordering CSPs to certain clustering problems, under the Unique Games Conjecture.   In a surprising convergence of algorithms and hardness results, the same work also leads to a generic algorithm that achieves the optimal approximation for every constraint satisfaction problem.

More from this channel