Simić, Petar D. (1991) Constrained Nets for Graph Matching and Other Quadratic Assignment Problems. Neural Computation, 3 (2). pp. 268281. ISSN 08997667. http://resolver.caltech.edu/CaltechAUTHORS:SIMnc91

PDF
 Published Version
See Usage Policy. 731Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:SIMnc91
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 (handdesigned) graphs of moderate size (20100 nodes) are discussed.
Item Type:  Article  

Related URLs: 
 
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 DEAC0381ER40050 and DEFG0385ER25009, the Office of the Program Manager of the Joint Tactical Fusion Office, and the NSF under Grant EET8700064.  
Funders: 
 
Issue or Number:  2  
Record Number:  CaltechAUTHORS:SIMnc91  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:SIMnc91  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  12331  
Collection:  CaltechAUTHORS  
Deposited By:  Sydney Garstang  
Deposited On:  12 Nov 2008 23:20  
Last Modified:  01 May 2015 19:31 
Repository Staff Only: item control page