Breaking Value Symmetry

Details Breaking Value Symmetry Breaking Value Symmetry

2009-03-06

arxiv.org/abs/0903.1146v1

Computer Science

Artificial Intelligence

Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, Sept

Scientific paper

One common type of symmetry is when values are symmetric. For example, if we are assigning colours (values) to nodes (variables) in a graph colouring problem then we can uniformly interchange the colours throughout a colouring. For a problem with value symmetries, all symmetric solutions can be eliminated in polynomial time. However, as we show here, both static and dynamic methods to deal with symmetry have computational limitations. With static methods, pruning all symmetric values is NP-hard in general. With dynamic methods, we can take exponential time on problems which static methods solve without search.

Affiliated with

Also associated with

No associations

Rating

Breaking Value Symmetry does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Breaking Value Symmetry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Breaking Value Symmetry will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-135651