Approximating the optimum: Efficient algorithms and their limits

Опубликовано 6 сентября 2016, 18:26

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.