Linear programming, width-1 CSPs, and robust satisfaction

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

doi:10.1145/2090236.2090274

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 proceeding › Conference 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 language	English (US)
Title of host publication	ITCS 2012 - Innovations in Theoretical Computer Science Conference
Pages	484-495
Number of pages	12
DOIs	https://doi.org/10.1145/2090236.2090274
State	Published - Feb 6 2012
Externally published	Yes
Event	3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States Duration: Jan 8 2012 → Jan 10 2012

Publication series

Name	ITCS 2012 - Innovations in Theoretical Computer Science Conference

Other

Other	3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012
Country	United States
City	Cambridge, MA
Period	1/8/12 → 1/10/12

Fingerprint

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 proceeding › Conference 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

@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 = feb

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",

note = "3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 ; Conference date: 08-01-2012 Through 10-01-2012",

}

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

T2 - 3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012

Y2 - 8 January 2012 through 10 January 2012

ER -

Access to Document

10.1145/2090236.2090274