Expected Gains from Parallelizing Constraint Solving for Hard Problems

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"}

Abstract

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)