Criticality and Parallelism in Combinatorial Optimization

William G. Macready, Athanassios G. Siapas and Stuart A. Kauffman

Working Papers from Santa Fe Institute

Abstract: We demonstrate the existence of a phase transition in combinatorial optimization problems. For many of these problems, as local search algorithms are parallelized, the quality of solutions first improves and then sharply degrades to no better than random search. This transition can be successfully characterized using finite-size scaling, a technique borrowed from statistical physics. We demonstrate our results for a family of generalized spin-glass models and the Traveling Salesman Problem. We determine critical exponents, investigate the effects of noise, and discuss conditions for the existence of the phase transition.

Date: 1995-06
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:95-06-054

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().