# Finding the minimum sum of a subset of entries of a given matrix with combinatorial constraints

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.

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.
• 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? Feb 13, 2019 at 22:39
• @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) Feb 14, 2019 at 0:21
• (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. Feb 14, 2019 at 0:23