SODA

Tractable symmetry breaking for CSPs with interchangeable values

Van Hentenryck, Pascal and Flener, Pierre and Pearson, Justin and Ågren, Magnus (2003) Tractable symmetry breaking for CSPs with interchangeable values. In: Proceedings of IJCAI'03, 9-15 Aug 2003, Acapulco, Mexico.

Full text not available from this repository.

Official URL: http://ijcai.org/Past%20Proceedings/IJCAI-2003/PDF...

Abstract

Symmetry breaking in CSPs has attracted considerable attention in recent years. Various general schemes have been proposed to eliminate symmetries during search. In general, these schemes may take exponential space or time to eliminate all symmetries. This paper studies classes of CSPs for which symmetry breaking is tractable. It identifies several CSP classes which feature various forms of value interchangeability and shows that symmetry breaking can be performed in constant time and space during search using dedicated search procedures. Experimental results also show the benefits of symmetry breaking on these CSPs, which encompass many practical applications.

Item Type:Conference or Workshop Item (Paper)
ID Code:3673
Deposited By:Magnus Ņgren
Deposited On:13 Oct 2009
Last Modified:18 Nov 2009 16:25

Repository Staff Only: item control page