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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00135540
Contributor : Christian Bessiere <>
Submitted on : Thursday, March 8, 2007 - 10:48:51 AM
Last modification on : Friday, October 30, 2020 - 12:04:02 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

657

Files downloads

312