ISSN:
1573-2878
Keywords:
Gradient flows
;
assignment problem
;
traveling salesman problem
;
graph partitioning problem
;
local search
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Over the past decade, a number of connections between continuous flows and numerical algorithms were established. Recently, Brockett and Wong reported a connection between gradient flows on the special orthogonal groupLO(n) and local search solutions for the assignment problem. In this paper, we describe a uniform formulation for certain NP-hard combinatorial optimization problems in matrix form and examine their connection with gradient flows onLO(n). For these problems, there is a correspondence between the so-called 2-opt solutions and asymptotically stable critical points of an associated gradient flow.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02192047
Permalink
