Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-066 | 17th April 2014 07:03

#### Robust Approximation of Temporal CSP

TR14-066
Authors: Suguru Tamaki, Yuichi Yoshida
Publication: 4th May 2014 00:03
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.