Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy

Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Research output: Contribution to journalArticle

5 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. We survey results that built upon this work.

Original languageEnglish (US)
Pages (from-to)615-648
Number of pages34
JournalComputational Complexity
Volume20
Issue number4
DOIs
StatePublished - Dec 1 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Algorithms
  • NP-complete problems
  • approximation
  • lift and project methods
  • lower bounds
  • matrix cut operators
  • proof complexity
  • random instances of 3SAT

Fingerprint Dive into the research topics of 'Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy'. Together they form a unique fingerprint.

  • Cite this