화학공학소재연구정보센터
Science, Vol.271, No.5245, 56-59, 1996
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 im proves 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.