Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INFINITE DOMAIN:
Reports tagged with infinite domain:
TR14-066 | 17th April 2014
Suguru Tamaki, Yuichi Yoshida

#### Robust Approximation of Temporal CSP

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

ISSN 1433-8092 | Imprint