Conference Publication Details
Mandatory Fields
Hebrard, E., O'Sullivan, B., Razgon, I.
Principles and Practice of Constraint Programming, 14th International Conference, CP 2008
A Soft Constraint of Equality: Complexity and Approximability
Scopus: 4 ()
Optional Fields
Peter J. Stukey
We introduce the SoftAllEqual global constraint, which maximizes the number of equalities holding between pairs of assignments to a set of variables. We study the computational complexity of propagating this constraint, showing that it is intractable in general, since maximizing the number of pairs of equally assigned variables in a set is NP-hard. We propose three ways of coping with NP-hardness. Firstly, we develop a greedy linear-time algorithm to approximate the maximum number of equalities within a factor of 2. Secondly, we identify a tractable (polynomial) class for this constraint. Thirdly, we identify a parameter based on this class and show that the SoftAllEqual constraint is fixed-parameter tractable with respect to this parameter. © 2008 Springer-Verlag Berlin Heidelberg.
Grant Details