Linear programming, width-1 CSPs, and robust satisfaction

Gabor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We say that an algorithm robustly decides a constraint satisfaction problem ε if it distinguishes at-least-(1 -ε)-satisfiable instances from less-than-(1 - r(ε))-satisfiable instances for some function r(ε) with r(ε) → 0 as ε → 0. In this paper we show that the canonical linear programming relaxation robustly decides ε if and only if ε has "width 1" (in the sense of Feder and Vardi).

Original languageEnglish (US)
Title of host publicationITCS 2012 - Innovations in Theoretical Computer Science Conference
Pages484-495
Number of pages12
DOIs
StatePublished - Feb 6 2012
Externally publishedYes
Event3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States
Duration: Jan 8 2012Jan 10 2012

Publication series

NameITCS 2012 - Innovations in Theoretical Computer Science Conference

Other

Other3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012
CountryUnited States
CityCambridge, MA
Period1/8/121/10/12

Keywords

  • approximation algorithm
  • constraint satisfaction problems
  • linear programming
  • robust satisfaction algorithm
  • width-1 CSPs

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Linear programming, width-1 CSPs, and robust satisfaction'. Together they form a unique fingerprint.

  • Cite this

    Kun, G., O'Donnell, R., Tamaki, S., Yoshida, Y., & Zhou, Y. (2012). Linear programming, width-1 CSPs, and robust satisfaction. In ITCS 2012 - Innovations in Theoretical Computer Science Conference (pp. 484-495). (ITCS 2012 - Innovations in Theoretical Computer Science Conference). https://doi.org/10.1145/2090236.2090274