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