Skip to Main content Skip to Navigation
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

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

Identifiers

Collections

Citation

Christian Bessière, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. Filtering algorithms for the NValue constraint. Constraints, Springer Verlag, 2006, 11 (4), pp.271-293. ⟨10.1007/s10601-006-9001-9⟩. ⟨lirmm-00135540⟩

Share

Metrics

Record views

684

Files downloads

390