### always_first's blog

By always_first, history, 7 years ago, translation, Hi everybody!

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 × m table select several numbers, maximizing their sum with following constraints: in each row the number of selected numbers is not less than Rmin and not more than Rmax, and for each column the number of selected numbers is not less than Cmin and not more than Cmax.

If Rmin = Rmax = 1 and Cmin = Cmax = 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 Rmin = Rmax = R, Cmin = Cmax = C)? Any thoughts would be greatly appreciated.  Comments (10)
 » Auto comment: topic has been translated by always_first (original revision, translated revision, compare)
 » In the case Rmin = Rmax = Cmin = 1, and general Cmax the problem reduces to Generalized assignment problem, which is NP-hard (and hard to approximate). I don't expect it to get any easier for general values of the bounds.However, this kind of problems are usally simple to transform to Integer Program, so if you're instance is not big you can hope to get an exact solution using a good MIP solver
•  » » Reduction is not correct since the problem you mentioned has a more strong weight constraint: "sum of costs of tasks cannot exceed the budget of an agent". In our case all weights in this constraint are equal to 1.
 » Isn't it a simple minimum cost LR-flow problem? Consider the classical bipartite graph where rows correspond to the left part and columns correspond to the right part, and there exist edges (r -> c, cost = A[r][c], 0 <= flow <= 1) for each row r, column c (s -> r, cost = 0, R_min <= flow <= R_max) for each row r (c -> t, cost = 0, C_min <= flow <= C_max) for each column c 
•  » » How do you enforce a minimum flow on each edge ?
•  » » » It is described in this topic, also the link to the paper is given.
•  » » Thank you! Nice solution.Does this solution work for not integer A[r][c] as well? In e-maxx site it is written that costs must be integers.
•  » » » There is no need for costs to be integer. Min-cost flow doesn't use the fact costs are integral at any moment.
•  » » » » I see, thanks a lot.
•  » » » » Hi. I know this is not related to the topic, but can you point me some good resources for min cost flow algorithms?Thanks!