Back to Search
Start Over
Filtering Algorithms for the NValue Constraint.
- Source :
- Integration of AI & OR Techniques in Constraint Programming for Combinatorial Optimization Problems; 2005, p79-93, 15p
- Publication Year :
- 2005
-
Abstract
- The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540261520
- Database :
- Supplemental Index
- Journal :
- Integration of AI & OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Publication Type :
- Book
- Accession number :
- 32978751
- Full Text :
- https://doi.org/10.1007/11493853_8