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