SODA

An O(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization

Beldiceanu, Nicolas and Carlsson, Mats and Petit, Thierry and Régin, Jean-Charles (2012) An O(n log n) Bound Consistency Algorithm for the Conjunction of an alldifferent and an Inequality between a Sum of Variables and a Constant, and its Generalization. In: ECAI.

Full text not available from this repository.

Official URL: http://dx.doi.org/10.3233/978-1-61499-098-7-145

Abstract

This paper gives an O(n log n) bound-consistency filtering algorithm for the conjunction alldifferent(V0,V1,…,Vn−1)∧ f(V0)⌖f(V1)⌖…⌖f(Vn−1) ≤ cst, (V0,V1,…,Vn−1,cst ∊ N+), where (N,⌖) is a commutative group, f is a unary function, and both ⌖ and f are monotone increasing. This complexity is equal to the complexity of the bound-consistency algorithm of the alldifferent constraint.

Item Type:Conference or Workshop Item (Paper)
ID Code:5353
Deposited By:Mats Carlsson
Deposited On:17 Jan 2013 11:48
Last Modified:17 Jan 2013 12:11

Repository Staff Only: item control page