CaltechAUTHORS
  A Caltech Library Service

Constrained Nets for Graph Matching and Other Quadratic Assignment Problems

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

[img]
Preview
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 (hand-designed) graphs of moderate size (20-100 nodes) are discussed.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1162/neco.1991.3.2.268DOIUNSPECIFIED
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.
Funders:
Funding AgencyGrant Number
Department of EnergyDE-AC03-81ER40050
Department of EnergyDE-FG03-85ER25009
National Science FoundationEET-8700064
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:26 Dec 2012 10:30

Repository Staff Only: item control page