Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-066 | 17th April 2014 07:03

Robust Approximation of Temporal CSP

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint