2026-07-22T00:10:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9679 2024-03-06T10:44:48Z ddc:004 open_access

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains Bodirsky, Manuel Mamino, Marcello Viola, Caterina Valued constraint satisfaction problems Piecewise linear functions Submodular functions Semilinear Constraint satisfaction Optimisation Model Theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Marcello Mamino and Caterina Viola 2018 Is Part Of LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2018.12 urn:nbn:de:0030-drops-96792 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.12 eng https://creativecommons.org/licenses/by/3.0/legalcode