×

Filtering algorithms for the NValue constraint. (English) Zbl 1114.68064

Summary: 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.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity

Software:

CHIP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Beldiceanu, N. (2001). Pruning for the Minimum Constraint Family and for the Number of Distinct Values Constraint Family. In T. Walsh (Ed.), Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming (CP-01), Paphos, Cyprus. Lecture Notes in Computer Science, volume 2239, pages 211–224. Berlin Heidelberg New York: Springer. · Zbl 1067.68611
[2] Beldiceanu, N., Carlsson, M., & Thiel, S. (2002). Cost-filtering Algorithms for the Two Sides of the Sum of Weights of Distinct Values Constraint. SICS Tech. Rep. T2002-14.
[3] Bessiere, C., Hebrard, E., Hnich, B., & Walsh, T. (2004). Tractability of global constraints. In M. Wallace (Ed.), Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP-04),Toronto, Canada. Lecture Notes in Computer Science, volume 3258 pages 716–720. Berlin Heideleberg New York: Springer. · Zbl 1152.68542
[4] Debruyne, R., & Bessière, C. (1997). Some Practicable Filtering Techniques for the Constraint Satisfaction Problem. In M.E. Pollack (Ed.), Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan. pages 412–417. San Mateo, California: Morgan Kaufmann.
[5] Dincbas, M., van Hentenryck, P., Simonis, H., & Aggoun, A. (1988). The constraint logic programming language CHIP. In Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Japan, (pp. 693–702). Tokyo, Japan: ICOT.
[6] Roy, P., & Pachet, F. (1999). Automatic Generation of Music Programs. In J. Jaffar (Ed.), Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming (CP-99), Alexandria, Virginia. Lecture Notes in Computer Science, volume 1713 pages 331–345. Berlin Heidelberg New York: Springer.
[7] Favaron, O., Mahéo, M., Saclé, J.-F. (1993). Some eigenvalue properties in graphs (Conjectures of graffiti - ii). Discrete Math. 111: 197–220. · Zbl 0785.05065 · doi:10.1016/0012-365X(93)90156-N
[8] Shahar, S., Even, G., Rawitz, D. (2004). Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95(22): 358–362.fs · Zbl 1184.68632
[9] Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. New York: W.H. Freeman. · Zbl 0411.68039
[10] Halldórsson, M., & Radhakrishnan, J. (1994). Greed is good: Approximating independent sets in sparse and bounded-degree graphs. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, Montréal, Québec, Canada, (pp. 439–448). New York: ACM Press. · Zbl 0866.68077
[11] Paschos, V. Th., & Demange, M. (1997). Improved approximations for maximum independent set via approximation chains. Appl. Math. Lett., 10: 105–110. · Zbl 0883.68067 · doi:10.1016/S0893-9659(97)00044-X
[12] Marzewski, E. (1945). Sur deux Propriétés des Classes d’Ensembles. Fund. Math. 33: 303–307.
[13] Östergard, P.R.J., & Weakley, W.D. (2001). Values of domination numbers of the queen’s graph. Electron. J. Comb. 8: 1–19. · Zbl 0973.05058
[14] Petit, T., Régin, J. C., & Bessiere, C. (2001). Specific Filtering Algorithms for Over-constrained Problems. In T. Walsh (Ed.), Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming (CP-01), Paphos, Cyprus. Lecture Notes in Computer Science, volume 2239 pages 451–463. Berlin Heidelberg New York: Springer. · Zbl 1067.68663
[15] Prosser, P. (1994). Binary Constraint Satisfaction Problems: some are harder than others. In A. G. Cohn (Ed.), Proceedings of the 11th European Conference on Artificial Intelligence (ECAI-94), Amsterdam, The Netherlands, pages 95–99. Chichester: Wiley.
[16] Régin, J. C. (1994). A Filtering Algorithm for Constraints of Difference in CSPs. In B. Hayes-Roth and R. E. Korf (Eds.), Proceedings of the 12th National Conference on Artificial Intelligence (AAAI-94), Seattle,Washington, pages 362–367. California: AAAI Press.
[17] Turán, P. (1941) On an extremal problem in graph theory. Mat. Fiz. Lapok 48: 436–452.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.