2
$\begingroup$

Given a real $n \times n$ matrix $A$ (feel free to assume its entries are non-negative, if it helps), what is known about the problem of computing the quantity $$ \max_{\sigma \in S_n} \left\{\sum_{j=1}^na_{j,\sigma(j)}\right\}? $$ (Here $S_n$ is the symmetric group, so we are maximizing over all permutations of the columns of $A$: if you like you can write the sum as $\mathrm{trace}(AP_\sigma)$, where $P_\sigma$ is the permutation matrix associated with the permutation $\sigma$).

For example, is it known to be NP-hard, or is there a known polynomial-time algorithm for computing it (maybe just for certain special classes of matrices)? Does it have a name and/or is it equivalent to a well-known problem? It feels vaguely graph isomorphism-ish to me, but I'm having trouble pinning it down.

As one minor note, numerical examples show that the greedy algorithm (i.e., pick the largest entry of $A$, then forget about that row and column and pick the largest entry of the remaining $(n-1) \times (n-1)$ submatrix, and repeat) does not always produce the maximum value even if $A$ is doubly stochastic.

$\endgroup$

1 Answer 1

10
$\begingroup$

This is the maximum weight matching problem in the weighted complete bipartite graph $K_{n,n}$, also known as the assignment problem. It does have a few polynomial-time algorithmic solutions.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.