1
$\begingroup$

I would like to know if the following problem is known and has any efficient solution.

Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no row or column is selected more than $b$ times.

This can be re-formulated as the following integer linear program: \begin{align} \mbox{maximize} &\sum_{1\le i,j\le n} s_{ij}x_{ij},\\ \mbox{subject to} & \sum_{1\le i,j\le n} x_{ij} = a,\\ & \sum_{1\le i\le n} x_{ij} \le b \quad\forall 1\le j\le n,\\ & \sum_{1\le j\le n} x_{ij} \le b \quad\forall 1\le i\le n,\\ & x_{ij}\in\{0,1\}\quad\forall 1\le i,j\le n. \end{align}

Thank you very much in advance for your help!

$\endgroup$
2
$\begingroup$

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and whose capacity is 1. Then add an edge of capacity $b$ from the source to each row, with cost 0, and similarly for the columns, and solve the resulting minimum cost flow problem -- which can be done in polynomial time.

Since all edge capacities are integers, stndard algorithms will return an optimal solution that is integral.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note: I think that you also need to put capacities of 1 on each row-to-column edge. And, for those who don't know, note that with this construction the edge capacities are integers, so standard algorithms will return an optimal integer flow, i.e., a solution to the given integer LP. $\endgroup$ – Neal Young Jun 25 at 19:52
  • $\begingroup$ @NealYoung, great points, thank you! I've edited my answer accordingly. $\endgroup$ – D.W. Jun 25 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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