Timeline for Finding the minimum sum of a subset of entries of a given matrix with combinatorial constraints
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14, 2019 at 0:43 | comment | added | Penelope Benenati | Thank you again! That's very useful and interesting. I was actually also wondering whether the problem I posted here about matrices is "strictly" more difficult than the original problem about computing the cost of a partition of coloured items, because I feel sure there exist no reduction from the matrix problem to the other one. | |
| Feb 14, 2019 at 0:23 | comment | added | Alex Meiburg | (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:21 | comment | added | Alex Meiburg | @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:11 | comment | added | Penelope Benenati | Thank you a lot! My problem here was the result of a reduction from another problem, which perhaps may be solved without the use of LP (maybe faster). I just posted the "other problem" (the original one) here, if you are interested (each element of the partition is represented by a column, and each color is represented by a row in the matrix of the above problem): mathoverflow.net/questions/323187/… | |
| Feb 13, 2019 at 23:14 | comment | added | Alex Meiburg | 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://… | |
| Feb 13, 2019 at 23:05 | comment | added | Alex Meiburg | 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. | |
| Feb 13, 2019 at 22:39 | comment | added | Penelope Benenati | 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:32 | vote | accept | Penelope Benenati | ||
| Feb 13, 2019 at 21:40 | history | answered | Alex Meiburg | CC BY-SA 4.0 |