Valued constraint satisfaction problems : hard and easy problems - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 1995

Valued constraint satisfaction problems : hard and easy problems


In order to deal with over-constrained Constraint Satisfaction Problems, various extensions of the CSP framework have been considered by taking into account costs, uncertainties, preferences, priorities... Each extension uses a specific mathematical operator (+, max...) to aggregate constraint violations. In this paper, we consider a simple algebraic framework, related to Partial Constraint Satisfaction, which subsumes most of these proposals and use it to characterize existing proposals in terms of rationality and computational complexity. We exhibit simple relationships between these proposals, try to extend some traditional CSP algorithms and prove that some of these extensions may be computationally expensive
Fichier principal
Vignette du fichier
083.pdf (285.11 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-02778456 , version 1 (18-01-2023)


  • HAL Id : hal-02778456 , version 1
  • PRODINRA : 122299


Thomas Schiex, Hélène Fargier, Gérard Verfaillie. Valued constraint satisfaction problems : hard and easy problems. 14th International joint conference on artificial intelligence (IJCAI 1995), International Joint Conferences on Artificial Intelligence Organization, Aug 1995, Montreal, Canada. pp.631-637. ⟨hal-02778456⟩
44 View
17 Download


Gmail Mastodon Facebook X LinkedIn More