Search Results

Documents authored by Viola, Caterina

Document
DOI: 10.4230/LIPIcs.MFCS.2020.85
The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains

Authors: Caterina Viola and Stanislav Živný

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over infinite-domains. This extends a result of Brakensiek and Guruswami [SODA'20] for promise (non-valued) CSPs (on finite domains).
Cite as

Caterina Viola and Stanislav Živný. The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 85:1-85:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{viola_et_al:LIPIcs.MFCS.2020.85,
  author =	{Viola, Caterina and \v{Z}ivn\'{y}, Stanislav},
  title =	{{The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{85:1--85:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.85},
  URN =		{urn:nbn:de:0030-drops-127566},
  doi =		{10.4230/LIPIcs.MFCS.2020.85},
  annote =	{Keywords: promise constraint satisfaction, valued constraint satisfaction, convex relaxations, polymorphisms}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.12
Submodular Functions and Valued Constraint Satisfaction Problems over Infinite Domains

Authors: Manuel Bodirsky, Marcello Mamino, and Caterina Viola

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.CSL.2018.12,
  author =	{Bodirsky, Manuel and Mamino, Marcello and Viola, Caterina},
  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 =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.12},
  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 Theory}
}
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