REVIEW Communicated by Douglas Miller Statistical Physics Algorithms That Converge

In recent years there has been significant interest in adapting tech-niques 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 shown experimentally to be successful there has been little theoretical analysis of them. In this paper we demonstrate connections between mean field theory methods and other approaches, in particular, barrier function and interior point methods. As an explicit example, we sum-marize our work on the linear assignment problem. In this previous work we defined a number of algorithms, including deterministic an-nealing, for solving the assignment problem. We proved convergence, gave bounds on the convergence times, and showed relations to other optimization algorithms. 1 Statistical Physics and Mean Field Theory for Optimization ~ In recent years there has been significant interest in adapting techniques from statistical physics, in particular mean field theory, to provide de-terministic heuristic algorithms for obtaining approximate solutions t