September 30, 2002

Constraint Programming 2002, Cornell

4

Related Work

nDecision problems:

nphase transitions in solvability, corresponding to hardness spike [Cheeseman et
al.; Selman et al.]

nsolution invariants: e.g., backbone [Gomes et al.]

nOptimization problems:

nexperimental:

•reduce to
decision problem [Zhang et al.]

•introduce
backbone concepts [Walsh et
al.]

ntheoretical:

•polynomial/exponential
transition in search algorithms [Zhang]

•predict A*
nodes expanded for problem distribution [Korf, Reid]

nLearning

ndynamic restart policies [Kautz et al.]