liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Min CSP on four elements: moving beyond submodularity
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2011 (English)In: Proceedings of the 17th international conference on Principles and practice of constraint programming / [ed] Jimmy Lee, Springer Berlin/Heidelberg, 2011, 438-453 p.Conference paper, Published paper (Refereed)
Abstract [en]

We report new results on the complexity of the valued constraint satisfaction problem (VCSP). Under the unique games conjecture, the approximability of finite-valued VCSP is fairly well-understood. However, there is yet no characterisation of VCSPs that can be solved exactly in polynomial time. This is unsatisfactory, since such results are interesting from a combinatorial optimisation perspective; there are deep connections with, for instance, submodular and bisubmodular minimisation. We consider the Min and Max CSP problems (i.e. where the cost functions only attain values in {0,1}) over four-element domains and identify all tractable fragments. Similar classifications were previously known for two- and three-element domains. In the process, we introduce a new class of tractable VCSPs based on a generalisation of submodularity. We also extend and modify a graph-based technique by Kolmogorov and Živný (originally introduced by Takhanov) for efficiently obtaining hardness results in our setting. This allow us to prove the result without relying on computer-assisted case analyses (which is fairly common when studying VCSPs). The hardness results are further simplified by the introduction of powerful reduction techniques.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2011. 438-453 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 6876
Keyword [en]
Constraint satisfaction problems, combinatorial optimisation, computational complexity, submodularity, bisubmodularity
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-74501DOI: 10.1007/978-3-642-23786-7_34ISBN: 978-3-642-23785-0 (print)OAI: oai:DiVA.org:liu-74501DiVA: diva2:486122
Conference
17th International Conference on Principles and Practice of Constraint Programming (CP'11)
Available from: 2012-01-30 Created: 2012-01-30 Last updated: 2017-02-23

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Jonsson, PeterKuivinen, FredrikThapper, Johan

Search in DiVA

By author/editor
Jonsson, PeterKuivinen, FredrikThapper, Johan
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf