Criticality and Parallelism in Combinatorial Optimization

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.