TR14-066 Authors: Suguru Tamaki, Yuichi Yoshida

Publication: 4th May 2014 00:03

Downloads: 1161

Keywords:

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