References

  1. Libor Barto, Andrei Krokhin & Ross Willard (2017): Polymorphisms, and how to use them. In: Andrei Krokhin & Stanislav Živný: The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups 7. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 1–44, doi:10.4230/DFU.Vol7.15301.1.
  2. S. Bistarelli, U. Montanari, F. Rossi, T. Schiex, G. Verfaillie & H. Fargier (1999): Semiring-based CSPs and valued CSPs: frameworks, properties, and comparison. Constraints 4, pp. 199–240, doi:10.1023/A:1026441215081.
  3. Stefano Bistarelli, Ugo Montanari & Francesca Rossi (1997): Semiring-based constraint satisfaction and optimization. Journal of the ACM 44, pp. 201–236, doi:10.1145/256303.256306.
  4. Manuel Bodirsky & Marcello Mamino (2017): Constraint satisfaction problems over numeric domains. In: Andrei Krokhin & Stanislav Živný: The Constraint Satisfaction Problem: Complexity and Approximability 7. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 79–111, doi:10.4230/DFU.Vol7.15301.79.
  5. Adrian Bondy & U.S.R. Murty (2008): Graph Theory. Springer-Verlag London.
  6. Lucas Bordeaux, Youssef Hamadi & Lintao Zhang (2006): Propositional satisfiability and constraint programming: a comparative survey. ACM Computing Surveys 38(4), doi:10.1145/1177352.1177354. Article 12.
  7. Andrei A. Bulatov (2006): A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM 53(1), pp. 66–120, doi:10.1145/1120582.1120584.
  8. Andrei A. Bulatov (2017): A dichotomy theorem for nonuniform CSPs. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pp. 319–330, doi:10.1109/FOCS.2017.37.
  9. Andrei A. Bulatov, Peter Jeavons & Andrei A. Krokhin (2005): Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing 34(3), pp. 720–742, doi:10.1137/S0097539700376676.
  10. Jin-Yi Cai & Xi Chen (2017): Complexity Dichotomies for Counting Problems. Cambridge University Press, doi:10.1017/9781107477063.
  11. David A. Cohen, Martin C. Cooper, PáidíCreed, Peter G. Jeavons & Stanislav Živný (2013): An algebraic theory of complexity for discrete optimization. SIAM Journal on Computing 42, pp. 1915–1939, doi:10.1137/130906398.
  12. Stephen A. Cook (1971): The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047.
  13. Nadia Creignou, Sanjeev Khanna & Madhu Sudan (2001): Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics, Pennsylvania, USA, doi:10.1137/1.9780898718546.
  14. Rina Dechter (2003): Constraint Processing. Morgan Kaufmann, California, USA, doi:10.1016/B978-1-55860-890-0.X5000-2.
  15. Tomás Feder & Moshe Y. Vardi (1998): The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing 28(1), pp. 57–104, doi:10.1137/S0097539794266766.
  16. Pavol Hell & Jaroslav Nesetril (2004): Graphs and Homomorphisms. Oxford University Press, doi:10.1093/acprof:oso/9780198528173.001.0001.
  17. John N. Hooker & W.-J. van Hoeve (2018): Constraint programming and operations research. Constraints 23, pp. 172–195, doi:10.1007/s10601-017-9280-3.
  18. Rostislav Horcík, Tommaso Moraschini & Amanda Vidal (2017): An algebraic approach to valued constraint satisfaction. In: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, doi:10.4230/LIPIcs.CSL.2017.42.
  19. Peter Jeavons (1998): On the algebraic structure of combinatorial problems. Theoretical Computer Science 200(1-2), pp. 185–204, doi:10.1016/S0304-3975(97)00230-2.
  20. Peter Jeavons, David A. Cohen & Marc Gyssens (1997): Closure properties of constraints. Journal of the ACM 44(4), pp. 527–548, doi:10.1145/263867.263489.
  21. Sebastian Kerkhoff (2012): A general Galois theory for operations and relations in arbitrary categories. Algebra Universalis 68(3), pp. 325–352, doi:10.1007/s00012-012-0209-9.
  22. Krzysztof C. Kiwiel (2001): Convergence and efficiency of subgradient methods for quasiconvex minimization. Mathematical Programming 90, pp. 1–25, doi:10.1007/PL00011414.
  23. Andrei Krokhin, Jakub Opršal, Marcin Wrochna & Stanislav Živný (2020): Topology and adjunction in promise constraint satisfaction. arXiv:2003.11351v2.
  24. Philippe Laborie, Jérǒme Rogerie, Paul Shaw & Petr Vilím (2018): IBM ILOG CP optimizer for scheduling. Constraints 23, pp. 210–250, doi:10.1007/s10601-018-9281-x.
  25. Richard E. Ladner (1975): On the structure of polynomial time reducibility. Journal of the ACM 22(1), pp. 155–171, doi:10.1145/321864.321877.
  26. F. William Lawvere (1973): Metric spaces, generalized logic, and closed categories. Rendiconti del seminario matématico e fisico di Milano XLIII, pp. 135–166, doi:10.1007/BF02924844. Also available online in Reprints in Theory and Applications of Categories, No. 1 (2001) pp. 1–37.
  27. F. William Lawvere (1984): State categories, closed categories, and the existence of semi-continuous entropy functions. IMA Preprint Series 86.
  28. Leonid Levin (1973): Universal search problems (in Russian). Problemy Peredachi Informatsii 9(3), pp. 115–116.
  29. Shinichi Mochizuki (2021): Inter-universal Teichmüller theory I: construction of Hodge theaters. Publications of the Research Institute for Mathematical Sciences 57(1), pp. 3–207, doi:10.4171/PRIMS/57-1-1.
  30. Reinhard Pöschel (1980): A General Galois Theory for Operations and Relations and Concrete Characterization of Related Algebraic Structures. Akademie der Wissenschaften der DDR Zentralinstitut für Mathematik und Mechanik. Report R-01/80.
  31. Kimmo I. Rosenthal (1991): Free quantaloids. Journal of Pure and Applied Algebra 72(1), pp. 67–82, doi:10.1016/0022-4049(91)90130-T.
  32. Kimmo I. Rosenthal (1996): The Theory of Quantaloids. Pitman Research Notes in Mathematics Series 348. CRC Press.
  33. Francesca Rossi, Peter van Beek & Toby Walsh (2006): Handbook of Constraint Programming. Elsevier Science, New York, USA.
  34. Thomas J. Schaefer (1978): The complexity of satisfiability problems. In: Proceedings of the 10th annual ACM Symposium on Theory of Computing, pp. 216–226, doi:10.1145/800133.804350.
  35. Alexander Schrijver (1998): Theory of Linear and Integer Programming. John Wiley & Sons.
  36. David Speyer & Bernd Sturmfels (2009): Tropical mathematics. Mathematics Magazine 82(3), pp. 163–173, doi:10.1080/0025570X.2009.11953615.
  37. Isar Stubbe (2005): Categorical structures enriched in a quantaloid: categories, distributors and functors. Theory and Applications of Categories 14(1), pp. 1–45.
  38. Edward Tsang (1993): Foundations of Constraint Satisfaction. Academic Pr, London and San Diego.
  39. Robert J. Vanderbei (2020): Linear Programming, 5th edition. Springer International Publishing, doi:10.1007/978-3-030-39415-8.
  40. Dmitriy Zhuk (2020): A proof of the CSP dichotomy conjecture.. Journal of the ACM 30, pp. 1–78, doi:10.1145/3402029.
  41. Stanislav Živný (2012): The Complexity of Valued Constraint Satisfaction Problems. Springer-Verlag Berlin Heidelberg, doi:10.1007/978-3-642-33974-5.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org