1
$\begingroup$

Recently I've learned hungarian algorithm for solving the assignment problem, Now I'm curious about how to solve more general problem: for given $n \times m$ table select several numbers, maximizing their sum with following constraints: in each row the number of selected numbers is not less than $R_{min}$ and not more than $R_{max}$, and for each column the number of selected numbers is not less than $C_{min}$ and not more than $C_{max}$.

If $R_{min} = R_{max} = 1$ and $C_{min} = C_{max} = 1$ this is the standard assignment problem. But what can we say about more general case? Any ideas about this (maybe, at least in case $R_{min} = R_{max} = R$, $C_{min} = C_{max} = C$)? Any thoughts would be greatly appreciated.

$\endgroup$
1
$\begingroup$

The general case can be modeled as a flow problem in a bipartite graph $G=(V_1\cup V_2,E)$, with $|V_1|=n$ and $|V_2|=m$.

To take into account your constraints, add a source $s$ and link to all vertices of $V_1$, and a sink $t$, linked to all vertices of $V_2$. Impose that the entering flow in each node of $V_1$ is at least $R_{min}$ and at most $R_{max}$, and that the exiting flow from each node of $V_2$ is at least $C_{min}$ and at most $C_{max}$, and you are done.

$\endgroup$

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.