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

Fingerprint

Constraint satisfaction problems
Linear programming

Keywords

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

ASJC Scopus subject areas

  • Computational Theory and Mathematics

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

Linear programming, width-1 CSPs, and robust satisfaction. / Kun, Gabor; O'Donnell, Ryan; Tamaki, Suguru; Yoshida, Yuichi; Zhou, Yuan.

ITCS 2012 - Innovations in Theoretical Computer Science Conference. 2012. p. 484-495 (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

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

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. ITCS 2012 - Innovations in Theoretical Computer Science Conference, pp. 484-495, 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012, Cambridge, MA, United States, 1/8/12. https://doi.org/10.1145/2090236.2090274
Kun G, O'Donnell R, Tamaki S, Yoshida Y, Zhou Y. Linear programming, width-1 CSPs, and robust satisfaction. In ITCS 2012 - Innovations in Theoretical Computer Science Conference. 2012. p. 484-495. (ITCS 2012 - Innovations in Theoretical Computer Science Conference). https://doi.org/10.1145/2090236.2090274
Kun, Gabor ; O'Donnell, Ryan ; Tamaki, Suguru ; Yoshida, Yuichi ; Zhou, Yuan. / Linear programming, width-1 CSPs, and robust satisfaction. ITCS 2012 - Innovations in Theoretical Computer Science Conference. 2012. pp. 484-495 (ITCS 2012 - Innovations in Theoretical Computer Science Conference).
@inproceedings{1b9f828346c74f9dbd5f9bf1d5ee432e,
title = "Linear programming, width-1 CSPs, and robust satisfaction",
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).",
keywords = "approximation algorithm, constraint satisfaction problems, linear programming, robust satisfaction algorithm, width-1 CSPs",
author = "Gabor Kun and Ryan O'Donnell and Suguru Tamaki and Yuichi Yoshida and Yuan Zhou",
year = "2012",
month = "2",
day = "6",
doi = "10.1145/2090236.2090274",
language = "English (US)",
isbn = "9781450311151",
series = "ITCS 2012 - Innovations in Theoretical Computer Science Conference",
pages = "484--495",
booktitle = "ITCS 2012 - Innovations in Theoretical Computer Science Conference",

}

TY - GEN

T1 - Linear programming, width-1 CSPs, and robust satisfaction

AU - Kun, Gabor

AU - O'Donnell, Ryan

AU - Tamaki, Suguru

AU - Yoshida, Yuichi

AU - Zhou, Yuan

PY - 2012/2/6

Y1 - 2012/2/6

N2 - 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).

AB - 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).

KW - approximation algorithm

KW - constraint satisfaction problems

KW - linear programming

KW - robust satisfaction algorithm

KW - width-1 CSPs

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

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

U2 - 10.1145/2090236.2090274

DO - 10.1145/2090236.2090274

M3 - Conference contribution

AN - SCOPUS:84863073195

SN - 9781450311151

T3 - ITCS 2012 - Innovations in Theoretical Computer Science Conference

SP - 484

EP - 495

BT - ITCS 2012 - Innovations in Theoretical Computer Science Conference

ER -