1 Search Results for "Vidal, Amanda"

Document
DOI: 10.4230/LIPIcs.CSL.2017.42
An Algebraic Approach to Valued Constraint Satisfaction

Authors: Rostislav Horcík, Tommaso Moraschini, and Amanda Vidal

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
We study the complexity of the valued CSP (VCSP, for short) over arbitrary templates, taking the general framework of integral bounded linearly order monoids as valuation structures. The class of problems considered here subsumes and generalizes the most common one in VCSP literature, since both monoidal and lattice conjunction operations are allowed in the formulation of constraints. Restricting to locally finite monoids, we introduce a notion of polymorphism that captures the pp-definability in the style of Geiger’s result. As a consequence, sufficient conditions for tractability of the classical CSP, related to the existence of certain polymorphisms, are shown to serve also for the valued case. Finally, we establish the dichotomy conjecture for the VCSP, modulo the dichotomy for classical CSP.
Cite as

Rostislav Horcík, Tommaso Moraschini, and Amanda Vidal. An Algebraic Approach to Valued Constraint Satisfaction. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{horcik_et_al:LIPIcs.CSL.2017.42,
  author =	{Horc{\'\i}k, Rostislav and Moraschini, Tommaso and Vidal, Amanda},
  title =	{{An Algebraic Approach to Valued Constraint Satisfaction}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.42},
  URN =		{urn:nbn:de:0030-drops-76767},
  doi =		{10.4230/LIPIcs.CSL.2017.42},
  annote =	{Keywords: Valued CSP, Polymorphism, pp-definability, Geiger’s Theorem.}
}
  • Refine by Author
  • 1 Horcík, Rostislav
  • 1 Moraschini, Tommaso
  • 1 Vidal, Amanda

  • Refine by Classification

  • Refine by Keyword
  • 1 Geiger’s Theorem.
  • 1 Polymorphism
  • 1 Valued CSP
  • 1 pp-definability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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 Imprint Privacy Contact