
TSpace at The University of Toronto Libraries >
School of Graduate Studies  Theses >
Doctoral >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1807/26271

Title:  Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations 
Authors:  Georgiou, Konstantinos 
Advisor:  Pitassi, Toniann 
Department:  Computer Science 
Keywords:  integrality gap lift and project systems convex optimization combinatorial optimization linear programming relaxations semidefinite programming relaxations minimum vertex cover constraint satisfaction problem Max Cut LovaszSchrijver system SheraliAdams system Lasserre system hardness of approximation 
Issue Date:  17Feb2011 
Abstract:  The inapproximability for NPhard combinatorial optimization problems lies in the heart of theoretical computer science. A negative result can be either conditional, where the starting point is a complexity assumption, or unconditional, where the inapproximability holds for a restricted model of computation.
Algorithms based on Linear Programming (LP) and Semidefinite Programming (SDP) relaxations are among the most prominent models of computation. The related and common measure of efficiency is the integrality gap, which sets the limitations of the associated algorithmic schemes. A number of systematic procedures, known as liftandproject systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the LovaszSchrijver (LS) and the SheraliAdams (SA) systems, or SDP relaxations, such as the LovaszSchrijver SDP (LS+), the SheraliAdams SDP (SA+) and the Lasserre (La) systems.
In this thesis we prove integrality gap lower bounds for the aforementioned liftandproject systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that liftandproject systems produce relaxations that have given the best algorithms known for a series of combinatorial problems, the lower bounds can be read as strong evidence of the inapproximability of the corresponding optimization problems. From the results found in the thesis we highlight the following:
For every epsilon>0, the levelOmega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2epsilon.
The integrality gap of the standard SDP for Vertex Cover remains 2o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP relaxations derived by the LS+ system. Finally, the addition of all ell1 inequalities eliminates all solutions not in the integral hull.
For every epsilon>0, the levelOmega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2epsilon. The integrality gap remains tight even for superconstantlevel SA+ relaxations.
We prove a tight lower bound for the number of tightenings that the SA system needs in order to prove the Pigeonhole Principle. We also prove sublinear and linear rank bounds for the La and SA systems respectively for the Tseitin tautology.
Linear levels of the SA+ system treat highly unsatisfiable instances of fixed predicateP constraint satisfaction problems over qary alphabets as fully satisfiable, when the satisfying assignments of the predicates P can be equipped with a balanced and pairwise independent distribution.
We study the performance of the Lasserre system on the cut polytope. When the input is the complete graph on 2d+1 vertices, we show that the integrality gap is at least 1+1/(4d(d+1)) for the leveld SDP relaxation. 
URI:  http://hdl.handle.net/1807/26271 
Appears in Collections:  Doctoral

This item is licensed under a Creative Commons License
Items in TSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
