Jj. Kosowsky et Al. Yuille, THE INVISIBLE HAND ALGORITHM - SOLVING THE ASSIGNMENT PROBLEM WITH STATISTICAL PHYSICS, Neural networks, 7(3), 1994, pp. 477-490
We propose a novel method for solving the assignment problem using tec
hniques adapted from statistical physics. We derive a convex effective
energy function whose unique minimum corresponds to the optimal assig
nment. Steepest descent results in a continuous-time dynamical system
that is guaranteed to converge arbitrarily close to the optimal soluti
on. Our algorithm has an appealing economic interpretation and has ver
y interesting connections to the discrete auction algorithm proposed b
y Bertsekas. We also derive an alternative discrete algorithm for mini
mizing the effective energy based on a theorem by Sinkhorn.