HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Rangarajan, A. Articles by Mjolsness, E. Search for Related Content PubMed PubMed Citation Articles by Rangarajan, A. Articles by Mjolsness, E.

Convergence Properties of the Softassign Quadratic Assignment Algorithm

Departments of Diagnostic Radiology and Electrical Engineering, Yale University, New Haven, CT 06520, U.S.A.

Alan Yuille

Smith-Kettlewell Eye Research Institute, San Francisco, CA 94115, U.S.A.

Eric Mjolsness

Jet Propulsion Laboratory, Pasadena, CA 91109, U.S.A.

The softassign quadratic assignment algorithm is a discrete-time, continuous-state, synchronous updating optimizing neural network. While its effectiveness has been shown in the traveling salesman problem, graph matching, and graph partitioning in thousands of simulations, its convergence properties have not been studied. Here, we construct discrete-time Lyapunov functions for the cases of exact and approximate doubly stochastic constraint satisfaction, which show convergence to a fixed point. The combination of good convergence properties and experimental success makes the softassign algorithm an excellent choice for neural quadratic assignment optimization.

This article has been cited by other articles:

				A. L. Yuille and A. Rangarajan The Concave-Convex Procedure Neural Comput., April 1, 2003; 15(4): 915 - 936. [Abstract] [Full Text] [PDF]

				C. Dang and L. Xu A Lagrange Multiplier and Hopfield-Type Barrier Function Method for the Traveling Salesman Problem Neural Comput., February 1, 2002; 14(2): 303 - 324. [Abstract] [Full Text] [PDF]