Document Open Access Logo

Robust Approximation of Temporal CSP

Authors Suguru Tamaki, Yuichi Yoshida

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.419.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Suguru Tamaki
Yuichi Yoshida

Cite As Get BibTex

Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 419-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.419

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.

Subject Classification

Keywords
  • constraint satisfaction
  • maximum satisfiability
  • approximation algorithm
  • hardness of approximation
  • infinite domain

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56(1-3):89-113, 2004. Google Scholar
  2. Libor Barto and Marcin Kozik. Robust satisfiability of constraint satisfaction problems. In Proc. 44th Symp. on Theory of Computing Conference (STOC), pages 931-940, 2012. Google Scholar
  3. Manuel Bodirsky. Constraint satisfaction with infinite domains. PhD thesis, Humboldt-Universität zu Berlin, 2004. Google Scholar
  4. Manuel Bodirsky. Complexity classification in infinite-domain constraint satisfaction. CoRR, abs/1201.0856, 2012. Google Scholar
  5. Manuel Bodirsky, Hubie Chen, and Michael Pinsker. The reducts of equality up to primitive positive interdefinability. J. Symb. Log., 75(4):1249-1292, 2010. Google Scholar
  6. Manuel Bodirsky and Jan Kára. The complexity of equality constraint languages. Theory Comput. Syst., 43(2):136-158, 2008. Google Scholar
  7. Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. J. ACM, 57(2), 2010. Google Scholar
  8. Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360-383, 2005. Google Scholar
  9. Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer, editors. Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar], volume 5250 of Lecture Notes in Computer Science. Springer, 2008. Google Scholar
  10. Víctor Dalmau and Andrei A. Krokhin. Robust satisfiability for CSPs: Hardness and algorithmic results. TOCT, 5(4):15, 2013. Google Scholar
  11. Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003. Google Scholar
  12. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  13. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979. Google Scholar
  14. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, and Moses Charikar. Beating the random ordering is hard: Every ordering CSP is approximation resistant. SIAM J. Comput., 40(3):878-914, 2011. Google Scholar
  15. Venkatesan Guruswami and Yuan Zhou. Tight bounds on the approximability of almost-satisfiable Horn SAT and Exact Hitting Set. Theory of Computing, 8(1):239-267, 2012. Google Scholar
  16. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  17. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pages 767-775, 2002. Google Scholar
  18. Subhash Khot. On the unique games conjecture (invited survey). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC), pages 99-121, 2010. Google Scholar
  19. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319-357, 2007. Google Scholar
  20. Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou. Linear programming, width-1 CSPs, and robust satisfaction. In Proceedings of the 3rd Innovations in Theoretical Computer Science (ITCS) conference, pages 484-495, 2012. Google Scholar
  21. Bernhard Nebel and Hans-Jürgen Bürckert. Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. J. ACM, 42(1):43-66, 1995. Google Scholar
  22. Prasad Raghavendra. Approximating NP-hard problems: Efficient algorithms and their limits. PhD thesis, University of Washington, 2009. Google Scholar
  23. Francesca Rossi, Peter van Beek, and Toby Walsh, editors. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Elsevier Science, 2006. Google Scholar
  24. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 216-226, 1978. Google Scholar
  25. David Steurer. Fast SDP algorithms for constraint satisfaction problems. In Proc. 21st Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 684-697, 2010. Google Scholar
  26. Peter van Beek. Reasoning about qualitative temporal information. Artif. Intell., 58(1-3):297-326, 1992. Google Scholar
  27. Marc Vilain, Henry Kautz, and Peter van Beek. Constraint propagation algorithms for temporal reasoning: A revised report. In Daniel S. Weld and Johan de Kleer, editors, Readings in Qualitative Reasoning about Physical Systems, pages 373-381, 1989. Google Scholar
  28. Uri Zwick. Finding almost-satisfying assignments. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC), pages 551-560, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact