2026-08-17T08:48:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4713 2024-03-06T10:35:17Z ddc:004 open_access

Robust Approximation of Temporal CSP Tamaki, Suguru Yoshida, Yuichi constraint satisfaction maximum satisfiability approximation algorithm hardness of approximation infinite domain 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Suguru Tamaki and Yuichi Yoshida 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.419 urn:nbn:de:0030-drops-47135 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.419 eng https://creativecommons.org/licenses/by/3.0/legalcode