Criticality and Parallelism in Combinatorial Optimization

See allHide authors and affiliations

Science  05 Jan 1996:
Vol. 271, Issue 5245, pp. 56-59
DOI: 10.1126/science.271.5245.56


Local search methods constitute one of the most successful approaches to solving large-scale combinatorial optimization problems. As these methods are increasingly parallelized, optimization performance initially improves but then abruptly degrades to no better than that of random search beyond a certain point. The existence of this transition is demonstrated for a family of generalized spin-glass models and the traveling salesman problem. Finite-size scaling is used to characterize size-dependent effects near the transition, and analytical insight is obtained through a mean-field approximation.