From: israel@math.ubc.ca (Robert Israel)
Subject: Re: Optimization challenge: reordering matrix rows to minimize diagonals
Date: 14 Sep 1999 21:45:34 GMT
Newsgroups: alt.sci.math.combinatorics,sci.math,sci.stat.math
Keywords: Assignment Problem

In article <7rdk3h$hss$1@winter.news.rcn.net>,
 "Jason Comander" <jcomand@mit.edu> writes:
> 
> Does anybody recognize this problem as something previously solved?  I am
> looking for an algorithm to solve it.  The problem evolved out of trying to
> track moving particles given an unordered list of their coordinates over
> time.
> 
> Given:
> 
> a list of (x,y) coordinates of N particles at time t=0 and
> a list of (x,y) coordinates of N particles at time t=1
> 
> The particles have moved slightly between time t=0 and t=1.
> 
> Challenge:  Match each coordinate from time t=0 with one from time t=1 so
> that the total movement observed between t=0 and t=1 is minimized.  Define
> "total movement observed" (or "minimized distance") however you like to make
> the problem easier to solve.  One example would be minimizing the sum over
> all matched pairs of the euclidian distance between the pair.

This is an example of what's known as an Assignment Problem.  More generally,
given a symmetric N x N matrix with entries a_{i,j}, you want to choose a 
permutation p of [1..N] to minimize sum_i a_{i,p(i)}.  There are efficient
ways of doing this - see most texts on Linear Programming or Operations
Research.  One way (not as efficient in theory, but handy if you have
access to linear programming software) is to represent this as a linear 
programming problem:

minimize sum_{i,j} a_{i,j} x_{i,j}
subject to sum_i x_{i,j} = 1 for each j
           sum_j x_{i,j} = 1 for each i
all x_{i,j} >= 0

and match i to j if x_{i,j} = 1 in the solution (there is always
an optimal solution in which all x_{i,j} are 0 or 1).


Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2