Valued Constraint Satisfaction Problems: Hard and Easy Problems
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 631-638.
Abstract
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.
@inproceedings{ijcai1995p83,
title = {Valued Constraint Satisfaction Problems: Hard and Easy Problems},
author = {Schiex, Thomas and Fargier, Helene and Verfaillie, Gérard},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {631--638},
year = {1995},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1995/83},
}
TY - CPAPER TI - Valued Constraint Satisfaction Problems: Hard and Easy Problems AU - Schiex, Thomas AU - Fargier, Helene AU - Verfaillie, Gérard T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 631 EP - 638 UR - https://ijcai.org/proceedings/1995/83 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
