0
$\begingroup$

Given a matrix $M\in\mathbb{N}^{n\times n}$, let $Z$ be the set of all the $M$'s entry subsets $S$ such that (i) no two entries of $S$ are on the same row or column of $M$ and (ii) $|S|=n$. Clearly we have $|Z|=n!$.

Question: How can we (efficiently) find the $M$'s entry subset $S^* \in Z$ whose element sum is the smallest over all the $M$'s entry subsets belonging to $Z$?

We are interested in finding one of $Z$'s element attaining the minimum of the above question when it is not unique. Furthermore, a method to (efficiently) obtain just the sum of the elements of $S^*$ (without necessarily finding $S^*$) would be a significant result.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Here is a way to formulate it as a convex optimization problem, which can then be solved in polynomial time. Your variables are $a_{i,j}$, one for each position in the matrix. The problem is then: $$0\le a_{i,j} \le 1$$ $$\forall_j \sum_i a_{i,j} = 1$$ $$\forall_i \sum_j a_{i,j} = 1$$ $$\textrm{Minimize } M\bullet a$$ The first constraint defines $a$ as binary variables, the second and third define your "one per row/col" rule, and the last is the linear objective function. This leaves off the mention that $a_{i,j}$ are integer: the values allowed by the above only restrict to the matrices $A$ that are doubly stochastic. However, the space of doubly stochastic matrices is the convex hull of permutation matrices, which are the ones you want. Thus, any linear objective function will naturally converge to a proper integer solution.

You can solve the above problem with any linear programming toolkit, such as GLPK, Gurobi, CPLEX...

There is a great deal of literature on the topic of optimizing over the space of permutation matrices, because they are such a convenient space to describe. e.g. https://www.di.ens.fr/~aspremon/PDF/Simons13.pdf

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you! I have a question. Assume the given matrix $M$ is not square, i.e. $M\in\mathbb{N}^{r\times c}$ with $c>r$, and the constraint (i) is the same, i.e. "no two entries of $S$ are on the same row or column", whereas the constraint (ii) is $|S|=r$. Is it possible to adapt the solution you propose to this problem extension? $\endgroup$
    – Penelope Benenati
    Commented Feb 13, 2019 at 22:39
  • 1
    $\begingroup$ I believe it will work as well, yes, although I'm not 100% at the moment. The relevant theorem that makes the above work for the square case is Birkhoff's theorem: every doubly stochastic matrix is a convex combination of permutation matrices. That statement, together with the fact that permutation matrices are all doubly stochastic, means any linear description such as the above will actually optimize over permutation matrices. For this to work in the rectangular case, you would need a similar statement to Birkhoff's theorem for these rectangular matrices. I believe it is true. $\endgroup$
    – Alex Meiburg
    Commented Feb 13, 2019 at 23:05
  • 2
    $\begingroup$ Found it. The generalized case is called the transportation polytope. Side 12 of this deck states that what you want is true: the straightforward modification of the above equations will yield an efficient algorithm. google.com/url?sa=t&source=web&rct=j&url=https://… $\endgroup$
    – Alex Meiburg
    Commented Feb 13, 2019 at 23:14
  • 1
    $\begingroup$ @PenelopeBenenati if you care particularly about efficiency, it's worth noting that this problem is actually just bipartite minimum matching (or maximum -- negate $M$), aka an Assignment problem. You're matching rows to columns, and the weight of each 'edge' is the entry in the matrix. This can be solved via e.g. the en.wikipedia.org/wiki/Hungarian_algorithm which runs in O(n^3) time (as opposed to worst-case O(n^7) for the LP). The rectangular variant is also bipartite maximum matching, in particular a Transport problem en.wikipedia.org/wiki/Transportation_theory_(mathematics) $\endgroup$
    – Alex Meiburg
    Commented Feb 14, 2019 at 0:21
  • 1
    $\begingroup$ (contd) and although I couldn't find any algorithms specifically for that, you can turn the rectangular maximum matching problem into a square maximum matching problem by adding $c-r$ new row with all zero entries, so that those new rows add no value. This is only efficient if $c/r$ is $O(1)$. For $c \gg r$, there are probably adaptations of the Hungarian algorithm that handle it efficiently. $\endgroup$
    – Alex Meiburg
    Commented Feb 14, 2019 at 0:23

You must log in to answer this question.

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