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 | |
| 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
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
}
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 -