License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2018.12
URN: urn:nbn:de:0030-drops-96792
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9679/
Go to the corresponding LIPIcs Volume Portal

Bodirsky, Manuel ; Mamino, Marcello ; Viola, Caterina

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains

pdf-format:
LIPIcs-CSL-2018-12.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{bodirsky_et_al:LIPIcs:2018:9679,
  author =	{Manuel Bodirsky and Marcello Mamino and Caterina Viola},
  title =	{{Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9679},
  URN =		{urn:nbn:de:0030-drops-96792},
  doi =		{10.4230/LIPIcs.CSL.2018.12},
  annote =	{Keywords: Valued constraint satisfaction problems, Piecewise linear functions, Submodular functions, Semilinear, Constraint satisfaction, Optimisation, Model Th}
}

Keywords: Valued constraint satisfaction problems, Piecewise linear functions, Submodular functions, Semilinear, Constraint satisfaction, Optimisation, Model Th
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI