|
Abstract : |
A new technique termed softassign, is applied to three combinatorial optimization problems---weighted graph matching, the traveling salesman problem and graph partitioning. Softassign, which has emerged from the recurrent neural network/statistical physics framework, enforces twoway (assignment) constraints without the use of penalty terms in the energy functions. The softassign can also be generalized from two-way winner-take-all constraints to multiple membership constraints which are required for graph partitioning. The softassign technique is compared to softmax (Potts glass) dynamics. Within the statistical physics framework, softmax and a penalty term has been a widely used method for enforcing the two-way constraints common to many combinatorial optimization problems. The benchmarks present evidence that softassign has clear advantages in accuracy, speed, parallelizability and algorithmic simplicity over softmax and a penalty term in optimization problems with two-way constraints. Softassign, Deterministic annealing, Combinatorial optimization, Graph matching, Traveling salesman problem, Graph partitioning., |
