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.
Improved algorithm for the soft global cardinality constraint
MILANO, MICHELA;
2006
Abstract
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.File in questo prodotto:
Eventuali allegati, non sono esposti
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
