Search T-Space Advanced Search
Home

Browse
Communities
& Collections

Issue Date
Author
Title
Subject

Sign on to:
Receive email
updates

My Account
authorized users

Edit Profile

Help
About T-Space
 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 gaplift and project systemsconvex optimizationcombinatorial optimizationlinear programming relaxationssemidefinite programming relaxationsminimum vertex coverconstraint satisfaction problemMax CutLovasz-Schrijver systemSherali-Adams systemLasserre systemhardness of approximation Issue Date: 17-Feb-2011 Abstract: The inapproximability for NP-hard 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 lift-and-project systems, have been proposed to improve the integrality gap of standard relaxations. These systems build strong hierarchies of either LP relaxations, such as the Lovasz-Schrijver (LS) and the Sherali-Adams (SA) systems, or SDP relaxations, such as the Lovasz-Schrijver SDP (LS+), the Sherali-Adams SDP (SA+) and the Lasserre (La) systems. In this thesis we prove integrality gap lower bounds for the aforementioned lift-and-project systems and for a number of combinatorial optimization problems, whose inapproximability is yet unresolved. Given that lift-and-project 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 level-Omega(sqrt(log n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon. The integrality gap of the standard SDP for Vertex Cover remains 2-o(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 level-Omega(sqrt(log n/ log log n)) SA relaxation of Vertex Cover has integrality gap 2-epsilon. The integrality gap remains tight even for superconstant-level 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 predicate-P constraint satisfaction problems over q-ary 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 level-d SDP relaxation. URI: http://hdl.handle.net/1807/26271 Appears in Collections: Doctoral

Files in This Item:

File Description SizeFormat
Georgiou_Konstantinos_201011_PhD_thesis.pdf1.67 MBAdobe PDF
View/Open

This item is licensed under a Creative Commons License

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.