Solving the Really Hard Problems with Cooperative Search

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 = "Solving the Really Hard Problems with Cooperative Search",
 BOOKTITLE = Proc. of AAAI93,
 PAGES = "231-236",
 PUBLISHER = "AAAI Press",
 ADDRESS = "Menlo Park, CA",
 YEAR = "1993"}

We present and experimentally evaluate the hypothesis that cooperative parallel search is well suited for hard graph coloring problems near a previously identified transition between under- and overconstrained instances. We find that simple cooperative methods can often solve such problems faster than the same number of independent agents.
postcript (183K)