NDLI: Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy

Content Provider	IEEE Xplore Digital Library
Author	Georgiou, K. Magen, A. Pitassi, T. Tourlakis, I.
Copyright Year	2007
Description	Author affiliation: Toronto Univ., Toronto (Georgiou, K.; Magen, A.; Pitassi, T.; Tourlakis, I.)
Abstract	Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is Vertex Cover. PCP-based techniques of Dinur and Safra [7] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP technicptes are the most promising methods available for improving upon this factor of 2. Following a line of study initiated by Arora et al. [3], our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for Vertex Cover better than 2. Lovasz and Schrijver [21] introduced the systems LS and $LS_{+}for$ systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, $LS_{+}$ captures the celebrated SDP-based algorithms for Max Cur and Sparsest Cur mentioned above. We rule out polynomial-time 2 - Omega(lfloor) approximations for Vertex Cover using $LS_{+}.$ In particular, we prove an integrality gap of 2 - o(lfloor)for Vertex Cover SDPs obtained by tightening the standard LP relaxation with Omega(radiclog n/ log log n) rounds of $LS_{+}.$ While tight integrality gaps were known for Vertex Cover in the weaker LS system [23 ], previous results did not rule out a2 - Omega(1) approximation after even two rounds of $LS_{+}.$
Starting Page	702
Ending Page	712
File Size	315842
Page Count	11
File Format	PDF
ISBN	9780769530109
ISSN	02725428
DOI	10.1109/FOCS.2007.35
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-10-21
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation algorithms Computer science Polynomials Educational institutions Linear programming NP-hard problem Erbium Greedy algorithms Design optimization Algorithm design and analysis
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Integrality gaps of 2 − o(1) for vertex cover sdps in the lovász-schrijver hierarchy (2006)

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the LovszSchrijver Hierarchy

Vertex cover resists sdps tightened by local hypermetric inequalities (2007).

Proving integrality gaps without knowing the linear program

Vertex Cover resists SDPs tightened by local hypermetric inequalities (2008)

New lower bounds for Vertex Cover in the Lovász-Schrijver hierarchy (2006)

Proving integrality gaps without knowing the linear program (2006)

Csc5160: combinatorial optimization and approximation algorithms topic: set cover date: 10/03/2008.

Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy

Similar Documents

Integrality gaps of 2 − o(1) for vertex cover sdps in the lovász-schrijver hierarchy (2006)

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the LovszSchrijver Hierarchy

Vertex cover resists sdps tightened by local hypermetric inequalities (2007).

Proving integrality gaps without knowing the linear program

Vertex Cover resists SDPs tightened by local hypermetric inequalities (2008)

New lower bounds for Vertex Cover in the Lovász-Schrijver hierarchy (2006)

Proving integrality gaps without knowing the linear program (2006)

Csc5160: combinatorial optimization and approximation algorithms topic: set cover date: 10/03/2008.

Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy