Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Mikhail Alekhnovich; Sanjeev Arora; Iannis Tourlakis

doi:10.1145/1060590.1060634

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Research output: Contribution to journal › Conference article › peer-review

36 Scopus citations

Abstract

Lovász and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT. and SPARSEST CUT). We prove strong inapproximability results in this model for well-known problems such as MAX-3SAT, HYPERGRAPH VERTEX COVER and SET COVER. We show that the relaxations produced by as many as Ω(n) rounds of the LS ₊ procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS ₊ approach gives even slightly subexponential approximation algorithms for these problems. We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.

Original language	English (US)
Pages (from-to)	294-303
Number of pages	10
Journal	Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/1060590.1060634
State	Published - 2005
Event	13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States Duration: Nov 7 2005 → Nov 11 2005

All Science Journal Classification (ASJC) codes

Software

Keywords

Inapproximability
Integrality gaps
Lovász-Schrijver matrix cuts

Access to Document

10.1145/1060590.1060634

Cite this

@article{8731e0c9b3204bf6aa28fea19ef4080b,

title = "Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy",

abstract = "Lov{\'a}sz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT. and SPARSEST CUT). We prove strong inapproximability results in this model for well-known problems such as MAX-3SAT, HYPERGRAPH VERTEX COVER and SET COVER. We show that the relaxations produced by as many as Ω(n) rounds of the LS + procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS + approach gives even slightly subexponential approximation algorithms for these problems. We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.",

keywords = "Inapproximability, Integrality gaps, Lov{\'a}sz-Schrijver matrix cuts",

author = "Mikhail Alekhnovich and Sanjeev Arora and Iannis Tourlakis",

year = "2005",

doi = "10.1145/1060590.1060634",

language = "English (US)",

pages = "294--303",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery (ACM)",

note = "13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications ; Conference date: 07-11-2005 Through 11-11-2005",

}

TY - JOUR

T1 - Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

AU - Alekhnovich, Mikhail

AU - Arora, Sanjeev

AU - Tourlakis, Iannis

PY - 2005

Y1 - 2005

N2 - Lovász and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT. and SPARSEST CUT). We prove strong inapproximability results in this model for well-known problems such as MAX-3SAT, HYPERGRAPH VERTEX COVER and SET COVER. We show that the relaxations produced by as many as Ω(n) rounds of the LS + procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS + approach gives even slightly subexponential approximation algorithms for these problems. We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.

AB - Lovász and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT. and SPARSEST CUT). We prove strong inapproximability results in this model for well-known problems such as MAX-3SAT, HYPERGRAPH VERTEX COVER and SET COVER. We show that the relaxations produced by as many as Ω(n) rounds of the LS + procedure do not allow nontrivial approximation, thus ruling out the possibility that the LS + approach gives even slightly subexponential approximation algorithms for these problems. We also point out why our results are somewhat incomparable to known inapproximability results proved using PCPs, and formalize several interesting open questions.

KW - Inapproximability

KW - Integrality gaps

KW - Lovász-Schrijver matrix cuts

UR - http://www.scopus.com/inward/record.url?scp=34848876396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34848876396&partnerID=8YFLogxK

U2 - 10.1145/1060590.1060634

DO - 10.1145/1060590.1060634

M3 - Conference article

AN - SCOPUS:34848876396

SN - 0737-8017

SP - 294

EP - 303

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications

Y2 - 7 November 2005 through 11 November 2005

ER -

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this