ECCC-Report TR14-066https://eccc.weizmann.ac.il/report/2014/066Comments and Revisions published for TR14-066en-usSun, 04 May 2014 00:03:53 +0300
Paper TR14-066
| Robust Approximation of Temporal CSP |
Suguru Tamaki,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2014/066A temporal constraint language $\Gamma$ is a set of relations with first-order definitions in $({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from $\Gamma$. CSP($\Gamma$) admits robust approximation if, for any $\varepsilon \geq 0$, given a $(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an assignment that satisfies at least a $(1-f(\varepsilon))$-fraction of constraints in polynomial time. Here, $f(\varepsilon)$ is some function satisfying $f(0)=0$ and $\lim\limits_{\varepsilon \to 0}f(\varepsilon)=0$.
Firstly, we give a qualitative characterization of robust approximability: Assuming the Unique Games Conjecture, we give a necessary and sufficient condition on $\Gamma$ under which CSP($\Gamma$) admits robust approximation. Secondly, we give a quantitative characterization of robust approximability: Assuming the Unique Games Conjecture, we precisely characterize how $f(\varepsilon)$ depends on $\varepsilon$ for each $\Gamma$. We show that our robust approximation algorithms can be run in almost linear time.Sun, 04 May 2014 00:03:53 +0300https://eccc.weizmann.ac.il/report/2014/066