1
$\begingroup$

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem?

Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation matrices $P$.

I have heard that there are several types of algorithms for these kinds of problems, like iterative improvement, simulated annealing, tabu search, genetic algorithms, evolution strategies, ant algorithms, and scatter search. I am looking for existing software.

|cite|improve this question
$\endgroup$
  • $\begingroup$ How big are the matrices $A$ and $B$, typically? $\endgroup$ – Geoff Oxberry Dec 26 '13 at 20:43
  • $\begingroup$ For vertex-ordering problems: for theoretical results try Flow Metrics (LP-based algorithms, subsequent theoretical improvements use SDPs). In practice, in my experience, the best approach for our problems was to use METIS (or in our case H-METIS) as the basis of a divide-and-conquer algorithm (nearly linear time), followed by iterations of local improvement. But that might not work for you depending on A and B. $\endgroup$ – Neal Young Dec 27 '13 at 0:18
  • $\begingroup$ What norm is this? I can think of a few thinks for $||A||$: least squares, max, etc. $\endgroup$ – john mangual Dec 27 '13 at 19:14
  • $\begingroup$ Thanks a lot for the answer, I will check METIS. The matrices will be up to 500 by 500. I will probably try with a few different norms and see what works best in my case. $\endgroup$ – user12383 Dec 27 '13 at 21:40
  • $\begingroup$ This is a combinatorial problem, not a quadratic program. The feasible set contains $n!$ elements. You're probably stuck with some heuristic to solve it. $\endgroup$ – Dominique Dec 28 '13 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.