License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.419
URN: urn:nbn:de:0030-drops-47135
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4713/
Go to the corresponding LIPIcs Volume Portal

Tamaki, Suguru ; Yoshida, Yuichi

Robust Approximation of Temporal CSP

pdf-format:
30.pdf (0.5 MB)

Abstract

A temporal constraint language G is a set of relations with first-order definitions in (Q; <). Let CSP(G) denote the set of constraint satisfaction problem instances with relations from G. CSP(G) admits robust approximation if, for any e >= 0, given a (1-e)-satisfiable instance of CSP(G), we can compute an assignment that satisfies at least a (1-f(e))-fraction of constraints in polynomial time. Here, f(e) is some function satisfying f(0)=0 and f(e) goes 0 as e goes 0.

Firstly, we give a qualitative characterization of robust approximability: Assuming the Unique Games Conjecture, we give a
necessary and sufficient condition on G under which CSP(G) admits
robust approximation. Secondly, we give a quantitative characterization of robust approximability: Assuming the Unique Games
Conjecture, we precisely characterize how f(e) depends on e for each
G. We show that our robust approximation algorithms can be run in
almost linear time.

BibTeX - Entry

@InProceedings{tamaki_et_al:LIPIcs:2014:4713,
  author =	{Suguru Tamaki and Yuichi Yoshida},
  title =	{{Robust Approximation of Temporal CSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{419--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4713},
  URN =		{urn:nbn:de:0030-drops-47135},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.419},
  annote =	{Keywords: constraint satisfaction, maximum satisfiability, approximation algorithm, hardness of approximation, infinite domain}
}

Keywords: constraint satisfaction, maximum satisfiability, approximation algorithm, hardness of approximation, infinite domain
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI