Bessiere, ChristianHebrard, EmmanuelHnich, BrahimKiziltan, ZeynepWalsh, Toby2023-06-162023-06-1620061383-71331572-9354https://doi.org/10.1007/s10601-006-9001-9https://hdl.handle.net/20.500.14365/9042nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems -- MAY 30-JUN 01, 2005 -- Prague, CZECH REPUBLICThe 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.eninfo:eu-repo/semantics/openAccessNVALUE constraintNP-hardATLEASTNVALUEATMOSTNVALUEpruninglinear relaxationglobal constraintsConference Object10.1007/s10601-006-9001-92-s2.0-33751507679