Criticality and parallelism in combinatorial optimization.
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.
Santa Fe Institute, NM 87501, USA.
W G
WG
Macready
A G
AG
Siapas
S A
SA
Kauffman
D000465:Algorithms; D015233:Models, Statistical; D013696:Temperature; D013816:Thermodynamics