STATISTICAL PHYSICS ALGORITHMS THAT CONVERGE

In recent years there has been significant interest in adapting techni ques from statistical physics, in particular mean field theory, to pro vide deterministic heuristic algorithms for obtaining approximate solu tions to optimization problems. Although these algorithms have been sh own experimentally to be successful there has been little theoretical analysis of them. In this paper we demonstrate connections between mea n field theory methods and other approaches, in particular, barrier fu nction and interior point methods. As an explicit example, we summariz e our work on the linear assignment problem. In this previous work we defined a number of algorithms, including deterministic annealing, for solving the assignment problem. We proved convergence, gave bounds on the convergence times, and showed relations to other optimization alg orithms.