Solving the Really Hard Problems with Cooperative Search

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

Abstract

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 (189K)