Improved algorithm for the soft global cardinality constraint

We propose two algorithms achieving generalized arc consistency for the soft global cardinality constraint with variable-based violation and with value-based violation. They are based on graph theory and their complexity is O(√nm) where n is the number of variables and m is the sum of the cardinalities of the domains. They improve previous algorithms that ran respectively in O(n(m + n log n)) and O((n + k)(m + n log n)) where k is the cardinality of the union of the domains.