New lower bounds for approximation algorithms in the Lovasz-Schrijver hierarchy.

摘要

Determining how well we can efficiently compute approximate solutions to NP-hard problems is of great theoretical and practical interest. Typically the famous PCP theorem is used for showing that a problem has no algorithms computing good approximations. Unfortunately, for many problem this approach has failed. Nevertheless, for such problems, we may instead be able to show that a large subclass of algorithms cannot compute good approximations.; This thesis takes this approach, concentrating on subclasses of algorithms defined by the LS and LS+ Lovasz-Schrijver hierarchies. These subclasses define hierarchies of algorithms where algorithms in higher levels (also called "rounds") require more time, but may compute better approximations. Algorithms in the LS hierarchy are based on linear programming relaxations while those in the more powerful LS+ hierarchy are based on semidefinite programming relaxations. Most known approximation algorithms lie within the first two-three levels of the LS+ hierarchy, including the recent celebrated approximation algorithms of Goemans-Williamson [27] and Arora-Rao-Vazirani [7] for MAX-CUT and SPARSEST-CUT, respectively. So understanding the power of these algorithm families seems important.; We obtain new lower bounds for the LS and LS + hierarchies for several important problems. In all cases the approximations we rule out in these hierarchies are not ruled out by known PCP-based arguments. Moreover, unlike PCP-based inapproximability results, all our results are unconditional and do not rely on any computational complexity assumptions.; The lower bounds we prove are as follows: (1) For VERTEX COVER we show that O(log n) rounds of LS are needed to obtain 2 - epsilon approximations and O(log 2 n) rounds are needed for 1.5 - epsilon approximations. (2) For MAX-3SAT and SET COVER we show that O(n) rounds of LS + are needed for any non-trivial approximation. (3) For hypergraph VERTEX COVER on rank-k hypergraphs we show that O( n) rounds of LS+ are needed for k - 1 - epsilon approximations. (4) For hypergraph VERTEX COVER on rank-k hypergraphs we show that O(log log n) rounds of LS are needed for k - epsilon approximations.