Filtering algorithms for the NValue constraint - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Constraints Year : 2006

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.
Fichier principal
Vignette du fichier
constraints06-nvalue.pdf (407.7 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00135540 , version 1 (08-03-2007)

Identifiers

Cite

Christian Bessiere, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. Filtering algorithms for the NValue constraint. Constraints, 2006, 11 (4), pp.271-293. ⟨10.1007/s10601-006-9001-9⟩. ⟨lirmm-00135540⟩
286 View
354 Download

Altmetric

Share

Gmail Facebook X LinkedIn More