Tad Hogg and Colin P. Williams
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com
@INPROCEEDINGS {,
AUTHOR = "Tad Hogg and Colin P. Williams",
TITLE = "Expected Gains from Parallelizing Constraint Solving for Hard Problems",
BOOKTITLE = "Proc. of 12th Natl. Conf. on Artificial Intelligence (AAAI94)",
PAGES = "1310-1315",
PUBLISHER = "AAAI Press",
ADDRESS = "Menlo Park, CA",
MONTH = "August",
YEAR = "1994"}
A number of recent studies have examined how the difficulty of various
NP-hard problems varies with simple parameters describing their
structure. In particular, they have identified parameter values that
distinguish regions with many hard problem instances from relatively
easier ones. In this paper we continue this work by examining
independent parallel search. Specifically, we evaluate the speedup as
function of connectivity and search difficulty for the particular case
of graph coloring with a standard heuristic search method. This requires
examining the full search cost distribution rather than just the more
commonly reported mean and variance. We also show similar behavior for a
single-agent search strategy in which the search is restarted whenever
it fails to complete within a specified cost bound.
postcript (1.1M, 6 pages)