The Complexity of Valued Constraint Satisfaction Problems in a Nutshell

Abstract : The valued constraint satisfaction problem was introduced by Schiex et al. [23] as a unifying framework for studying constraint programming with soft constraints. A systematic worst-case complexity theoretical investigation of this problem was initiated by Cohen et al. [4], building on ideas from the successful classi cation programme for the ordinary constraint satisfaction problem. In addition to the decision problem for constraint satisfaction, this framework also captures problems as varied as Max CSP and integer programming with bounded domains. This paper is intended to give a quick introduction to the questions, the main results, and the current state of the complexity classi cation of valued constraint satisfaction problems. Two special cases are looked at in some detail : the classi cation for the Boolean domain and the less well-understood case of Max CSP. Some recent results for general constraint languages are also reviewed, as well as the connection to the very active study of approximation algorithms for Max CSP.
Type de document :
Communication dans un congrès
Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00830467
Contributeur : Ist Inria Saclay <>
Soumis le : mercredi 5 juin 2013 - 10:34:40
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : vendredi 6 septembre 2013 - 04:10:40

Fichier

paper_22.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00830467, version 1

Collections

Citation

Johan Thapper. The Complexity of Valued Constraint Satisfaction Problems in a Nutshell. Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00830467〉

Partager

Métriques

Consultations de la notice

99

Téléchargements de fichiers

177