2
$\begingroup$

I have a problem that is really important for my thesis and i am not studding math so i will be very glad if you help me in this case... thanks for your help in advance

I want to find permutation matrix $P$ which minimizes $\mathrm{trace}(P C P^T D)$, when $C$ and $D$ are given quadratic symmetric matrices.

sorry if its not clear enough

in the link below i found a similar question but there is a bit difference and that is that here we work with permutation matrices.but sorrily i can not come to conclusion:(

https://math.stackexchange.com/q/239352/200836

Improve this question
$\endgroup$
3
  • $\begingroup$ What does that minimization problem mean? Are you minimizing some kind of a matrix norm? Take a look at this formatting guide to make the question clearer: meta.math.stackexchange.com/q/5020/166535 $\endgroup$
    – Joonas Ilmavirta
    Commented Dec 12, 2014 at 20:44
  • $\begingroup$ thanks for your comment, we have C and D matrices and we want to find permutation which minimizes the Trace. is there any better way than checking all permutation matrices? $\endgroup$
    – math2014
    Commented Dec 12, 2014 at 21:42
  • 1
    $\begingroup$ I edited your question into a more standard form. For one thing, never use $I$ for any matrix other than an identity matrix unless you want to confuse every mathematician who is watching. I think your question is quite hard. $\endgroup$
    – Brendan McKay
    Commented Dec 12, 2014 at 23:54

1 Answer 1

Reset to default
6
$\begingroup$

This is the well-known problem: http://en.wikipedia.org/wiki/Quadratic_assignment_problem

In general there is no efficient algorithm known for this problem. A much more famous Travelling Salesman Problem is a particular case...

Improve this answer
$\endgroup$
4
  • $\begingroup$ is there any better way than checking all possible permutations? $\endgroup$
    – math2014
    Commented Dec 14, 2014 at 8:52
  • $\begingroup$ well, there was a lot of research done on this problem. it would not be necessary to check a fraction of all permutations of n symbols, but still nobody knows how to check less than exponentially (in terms of n) many of them. $\endgroup$
    – Dima Pasechnik
    Commented Dec 14, 2014 at 9:21
  • 2
    $\begingroup$ i.e. instead of n! permutations you might still need to check something like $2^n$ of them. $\endgroup$
    – Dima Pasechnik
    Commented Dec 14, 2014 at 9:24
  • $\begingroup$ you might like to check out arxiv.org/abs/1403.7721 for up to date references etc $\endgroup$
    – Dima Pasechnik
    Commented Dec 14, 2014 at 9:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .