Constrained Nets for Graph Matching and Other Quadratic Assignment Problems
- Creators
- Simić, Petar D.
Abstract
Some time ago Durbin and Willshaw proposed an interesting parallel algorithm (the "elastic net") for approximately solving some geometric optimization problems, such as the Traveling Salesman Problem. Recently it has been shown that their algorithm is related to neural networks of Hopfield and Tank, and that they both can be understood as the semiclassical approximation to statistical mechanics of related physical models. The main point of the elastic net algorithm is seen to be in the way one deals with the constraints when evaluating the effective cost function (free energy in the thermodynamic analogy), and not in its geometric foundation emphasized originally by Durbin and Willshaw. As a consequence, the elastic net algorithm is a special case of the more general physically based computations and can be generalized to a large class of nongeometric problems. In this paper we further elaborate on this observation, and generalize the elastic net to the quadratic assignment problem. We work out in detail its special case, the graph matching problem, because it is an important problem with many applications in computational vision and neural modeling. Simulation results on random graphs, and on structured (hand-designed) graphs of moderate size (20-100 nodes) are discussed.
Additional Information
© 1991 Massachusetts Institute of Technology. Received 2 August 1990; accepted 24 January 1991. I thank J. Hopfield, and S. Judd for useful conversations. The indirect inspiration for this paper came also from some conversations with D. Willshaw. This work was supported in part by the DOE under Grants DE-AC03-81ER40050 and DE-FG03-85ER25009, the Office of the Program Manager of the Joint Tactical Fusion Office, and the NSF under Grant EET-8700064.Attached Files
Published - SIMnc91.pdf
Files
Name | Size | Download all |
---|---|---|
md5:784ddb105703299d4168ca544eeb4718
|
748.8 kB | Preview Download |
Additional details
- Eprint ID
- 12331
- Resolver ID
- CaltechAUTHORS:SIMnc91
- DE-AC03-81ER40050
- Department of Energy (DOE)
- DE-FG03-85ER25009
- Department of Energy (DOE)
- EET-8700064
- NSF
- Created
-
2008-11-12Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field