Document Open Access Logo

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains

Authors Manuel Bodirsky, Marcello Mamino, Caterina Viola

PDF
Thumbnail PDF

File

LIPIcs.CSL.2018.12.pdf
  • Filesize: 0.51 MB
  • 22 pages

Document Identifiers

Author Details

Manuel Bodirsky
  • Institut für Algebra, Technische Universität Dresden, Germany
Marcello Mamino
  • Dipartimento di Matematica, Università di Pisa, Italy
Caterina Viola
  • Institut für Algebra, Technische Universität Dresden, Germany

Funding

  • Bodirsky, Manuel: The first and second author have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 681988, CSP-Infinity). The first author has also received funding from the DFG (Project number 622397)
  • Viola, Caterina: This author is supported by DFG Graduiertenkolleg 1763 (QuantLA).

Cite As Get BibTex

Manuel Bodirsky, Marcello Mamino, and Caterina Viola. Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CSL.2018.12

Abstract

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. It is desirable to classify the computational complexity of VCSPs depending on a fixed set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified in this sense. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. We remark that in this paper the infinite domain will always be the set of rational numbers. We show that such VCSPs can be solved in polynomial time when the cost functions are additionally submodular, and that this is indeed a maximally tractable class: adding any cost function that is not submodular leads to an NP-hard VCSP.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Mathematical optimization
  • Theory of computation → Complexity theory and logic
Keywords
  • Valued constraint satisfaction problems
  • Piecewise linear functions
  • Submodular functions
  • Semilinear
  • Constraint satisfaction
  • Optimisation
  • Model Theory

Metrics

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

References

  1. Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale. Complexity and real computation. Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. Google Scholar
  2. Manuel Bodirsky and Martin Grohe. Non-dichotomies in constraint satisfaction complexity. In Luca Aceto, Ivan Damgard, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, pages 184-196. Springer Verlag, July 2008. Google Scholar
  3. Manuel Bodirsky, Dugald Macpherson, and Johan Thapper. Constraint satisfaction tractability from semi-lattice operations on infinite sets. Transaction of Computational Logic (ACM-TOCL), 14(4):1-30, 2013. Google Scholar
  4. Manuel Bodirsky and Marcello Mamino. Tropically convex constraint satisfaction. Theory of Computing Systems, pages 1-29, 2017. An extended abstract of the paper appeared under the title "Max-Closed Semilinear Constraints" in the proceedings of CSR'16; preprint available under ArXiv:1506.04184. Google Scholar
  5. Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Google Scholar
  6. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330, 2017. Google Scholar
  7. David A Cohen, Martin C Cooper, Peter G Jeavons, and Andrei A Krokhin. The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11):983-1016, 2006. Google Scholar
  8. Jeanne Ferrante and Charles Rackoff. A decision procedure for the first order theory of real addition with order. SIAM Journal on Computing, 4(1):69-76, 1975. Google Scholar
  9. Satoru Fujishige. Submodular Functions and Optimization. volume 58 of Annals of Discrete Mathematics. North-Holland, Amsterdam, 2005. 2nd edition. Google Scholar
  10. M. Grötschel, L. Lovász, and L. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg, 1994. 2nd edition. Google Scholar
  11. Satoru Iwata and James B. Orlin. A simple combinatorial algorithm for submodular function minimization. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '09, pages 1230-1237, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1496770.1496903.
  12. Peter Jonsson, Fredrik Kuivinen, and Johan Thapper. Min CSP on four elements: Moving beyond submodularity. In Principles and Practice of Constraint Programming - CP 2011 - 17th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings, pages 438-453, 2011. Google Scholar
  13. Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolinek. The complexity of general-valued csps. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1246-1258, 2015. Google Scholar
  14. Vladimir Kolmogorov, Johan Thapper, and Stanislav Zivny. The power of linear programming for general-valued csps. SIAM J. Comput., 44(1):1-36, 2015. Google Scholar
  15. Marcin Kozik and Joanna Ochremiak. Algebraic properties of valued constraint satisfaction problem. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 846-858, 2015. Google Scholar
  16. Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80(2):346-355, 2000. Google Scholar
  17. Lou van den Dries. Tame topology and o-minimal structures, volume 248 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1998. URL: http://dx.doi.org/10.1017/CBO9780511525919.
  18. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342, 2017. 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