Limitations of Linear and Semidefinite Programs
Grant Robert Schoenebeck
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2010-119
August 21, 2010
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-119.pdf
NP-complete combinatorial optimization problems are important and well-studied, but remain largely enigmatic in fundamental ways. While efficiently finding the optimal solution to such a problem requires that P = NP, we can try to find approximately optimal solutions. To date, the most promising approach for approximating many combinatorial optimization problems has been semidefinite programming, a generalization of linear programming. However semidefinite programs are not as well understood as linear programs. An important question is whether semidefinite (or linear) programs can be improved to create better algorithms. <p> Several processes--Lovasz-Schrijver+ (LS+) [LS91] and the stronger Lasserre hierarchy [L01] for semidefinite programs, and Lovasz-Schrijver (LS) [LS91], and the stronger Sherali-Adams hierarchy [SA90] for linear programs--were create to systematically improve semidefinite and linear programs at the cost of additional runtime. This thesis studies the question: ``What is the tradeoff between the efficiency and the guaranteed approximation in these hierarchies?" These systems proceed in rounds (and thus are usually referred to as hierarchies) and all have in common that after <i>n</i> rounds, where <i>n</i> is the number of variables, they find the optimal solution, and they take time <i>n^{O(r)}</i> to run until the <i>r</i>th round. An ``integrality gap" of <i>\alpha</i> after <i>r</i> rounds for one of these hierarchies proves that the algorithms generated by the hierarchy cannot find an <i>\alpha</i> approximate solution in time <i>n^{\Omega (r)}</i>. <p> Unlike NP-hardness results, these results are unconditional, yet apply only to a large, but restricted, class of algorithms. However, very low levels of these hierarchies include some of the most celebrated approximation algorithms for NP-complete problems. For example, the first level of LS+ (and hence also Lasserre) for the IndependentSet problem implies the Lovasz <i>\theta</i>-function [L79] and for the MaxCut problem gives the Goemans-Williamson relaxation [GW94]. The ARV relaxation of the SparsestCut [ARV04] problem is no stronger than the relaxation given in the second level of LS+ (and hence also Lasserre). <p> This thesis shows an optimal integrality gap of <i>2-\epsilon</i> for <i>\Omega(n)</i> rounds the LS hierarchy relaxation of the VertexCover and MaxCut problems. This result implies that a very large class of linear programs require exponential time to solve VertexCover (or MaxCut) to better than a factor of 2, even on random graphs. The previously best known <i>2-\epsilon</i> integrality gap for VertexCover [ABLT06] only survived <i>\Omega(\log(n))</i> round of LS, and the previously best known <i>1/2+\epsilon</i> integrality gap for MaxCut [dVK07] survived any constant number of rounds of SA (and for thus LS). These results were the first to illustrate the stark difference between linear program relaxations and semidefinite program relaxations (because MaxCut is better approximated after just one round by LS+). <p> Additionally this thesis shows that even after <i>\Omega(n)</i> rounds, the Lasserre hierarchy cannot refute a random 3XOR formula. This is the first non-trivial integrality gap for the Lasserre hierarchy, the strongest of all the aforementioned hierarchies. As mentioned above, this result unconditionally rules out the possibility of a subexponential time algorithm for random 3-SAT over a large range of semidefinite programs. There are, additionally, many immediate corollaries such as a similar integrality gap of <i>7/6 - \epsilon</i> for VertexCover. The techniques in the thesis remain the only known way of obtaining integrality gaps for Lasserre.
Advisors: Luca Trevisan
BibTeX citation:
@phdthesis{Schoenebeck:EECS-2010-119,
Author= {Schoenebeck, Grant Robert},
Title= {Limitations of Linear and Semidefinite Programs},
School= {EECS Department, University of California, Berkeley},
Year= {2010},
Month= {Aug},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-119.html},
Number= {UCB/EECS-2010-119},
Abstract= {NP-complete combinatorial optimization problems are important and well-studied, but remain largely enigmatic in fundamental ways. While efficiently finding the optimal solution to such a problem requires that P = NP, we can try to find approximately optimal solutions. To date, the most promising approach for approximating many combinatorial optimization problems has been semidefinite programming, a generalization of linear programming. However semidefinite programs are not as well understood as linear programs. An important question is whether semidefinite (or linear) programs can be improved to create better algorithms.
<p>
Several processes--Lovasz-Schrijver+ (LS+) [LS91] and the stronger Lasserre hierarchy [L01] for semidefinite programs, and Lovasz-Schrijver (LS) [LS91], and the stronger Sherali-Adams hierarchy [SA90] for linear programs--were create to systematically improve semidefinite and linear programs at the cost of additional runtime. This thesis studies the question: ``What is the tradeoff between the efficiency and the guaranteed approximation in these hierarchies?" These systems proceed in rounds (and thus are usually referred to as hierarchies) and all have in common that after <i>n</i> rounds, where <i>n</i> is the number of variables, they find the optimal solution, and they take time <i>n^{O(r)}</i> to run until the <i>r</i>th round. An ``integrality gap" of <i>\alpha</i> after <i>r</i> rounds for one of these hierarchies proves that the algorithms generated by the hierarchy cannot find an <i>\alpha</i> approximate solution in time <i>n^{\Omega (r)}</i>.
<p>
Unlike NP-hardness results, these results are unconditional, yet apply only to a large, but restricted, class of algorithms. However, very low levels of these hierarchies include some of the most celebrated approximation algorithms for NP-complete problems. For example, the first level of LS+ (and hence also Lasserre) for the IndependentSet problem implies the Lovasz <i>\theta</i>-function [L79] and for the MaxCut problem gives the Goemans-Williamson relaxation [GW94]. The ARV relaxation of the SparsestCut [ARV04] problem is no stronger than the relaxation given in the second level of LS+ (and hence also Lasserre).
<p>
This thesis shows an optimal integrality gap of <i>2-\epsilon</i> for <i>\Omega(n)</i> rounds the LS hierarchy relaxation of the VertexCover and MaxCut problems. This result implies that a very large class of linear programs require exponential time to solve VertexCover (or MaxCut) to better than a factor of 2, even on random graphs. The previously best known <i>2-\epsilon</i> integrality gap for VertexCover [ABLT06] only survived <i>\Omega(\log(n))</i> round of LS, and the previously best known <i>1/2+\epsilon</i> integrality gap for MaxCut [dVK07] survived any constant number of rounds of SA (and for thus LS). These results were the first to illustrate the stark difference between linear program relaxations and semidefinite program relaxations (because MaxCut is better approximated after just one round by LS+).
<p>
Additionally this thesis shows that even after <i>\Omega(n)</i> rounds, the Lasserre hierarchy cannot refute a random 3XOR formula. This is the first non-trivial integrality gap for the Lasserre hierarchy, the strongest of all the aforementioned hierarchies. As mentioned above, this result unconditionally rules out the possibility of a subexponential time algorithm for random 3-SAT over a large range of semidefinite programs. There are, additionally, many immediate corollaries such as a similar integrality gap of <i>7/6 - \epsilon</i> for VertexCover. The techniques in the thesis remain the only known way of obtaining integrality gaps for Lasserre.},
}
EndNote citation:
%0 Thesis %A Schoenebeck, Grant Robert %T Limitations of Linear and Semidefinite Programs %I EECS Department, University of California, Berkeley %D 2010 %8 August 21 %@ UCB/EECS-2010-119 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-119.html %F Schoenebeck:EECS-2010-119