[R] A combinatorial optimization problem: finding the best permutation of a complex vector

[Ravi Varadhan]

Hi,

I have a complex-valued vector X in C^n.  Given another complex-valued vector Y in C^n, I want to find a permutation of Y, say, Y*,  that minimizes ||X - Y*||, the distance between X and Y*.  

Note that this problem can be trivially solved for "Real" vectors, since real numbers possess the ordering property. Complex numbers, however, do not possess this property.  Hence the challenge.

The obvious solution is to enumerate all the permutations of Y and pick out the one that yields the smallest distance.  This, however, is only feasible for small n.  I would like to be able to solve this for n as large as 100 - 1000, in which cases the permutation approach is infeasible. 

I am looking for algorithms, possibly iterative, that can provide a "good" approximate solutions that are not necessarily optimal for high-dimensional vectors. I can do random sampling, but this can be very inefficient in high-dimensional problems.   I am looking for efficient algorithms because this step has to be performed in each iteration of an "outer" algorithm.

Are there any clever adaptive algorithms out there?

Here is an example illustrating the problem:

require(e1071)

n <- 8
x <- runif(n) + 1i * runif(n)
y <- runif(n) + 1i * runif(n)

dist <- function(x, y) sqrt(sum(Mod(x - y)^2))

perms <- permutations(n)  
dim(perms)  # [1] 40320     8
tmp <- apply(perms, 1, function(ord) dist(x, y[ord]))
z <- y[perms[which.min(tmp), ]]  # exact solution
dist(x, z)

# an aproximate random-sampling approach
nsamp <- 10000  
perms <- t(replicate(nsamp, sample(1:n, size=n, replace=FALSE)))
tmp <- apply(perms, 1, function(ord) dist(x, y[ord]))
z.app <- y[perms[which.min(tmp), ]]  # approximate solution
dist(x, z.app)

Thanks for any help.

Best,
Ravi.


____________________________________________________________________

Ravi Varadhan, Ph.D.
Assistant Professor,
Division of Geriatric Medicine and Gerontology
School of Medicine
Johns Hopkins University

Ph. (410) 502-2619
email: rvaradhan at jhmi.edu