 |
HAL-LIRMM - Open Archive |  |
Journal articles
Filtering algorithms for the NValue constraint
Abstract : The NValue constraint 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.
Cited literature [16 references]
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00135540
Contributor : Christian Bessiere Connect in order to contact the contributor
Submitted on : Thursday, March 8, 2007 - 10:48:51 AM
Last modification on : Monday, October 11, 2021 - 1:24:06 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 10:26:37 PM
Contributor : Christian Bessiere Connect in order to contact the contributor
Submitted on : Thursday, March 8, 2007 - 10:48:51 AM
Last modification on : Monday, October 11, 2021 - 1:24:06 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 10:26:37 PM