Problem Detail: This came up while I was trying to answer this question on Wiring Length Minimization. I was going to call this the “polygamous marriage” problem, but the internet, so kittens. Yay! Suppose we have $M$ kittens that need to be adopted by $N$ people, $M > N$. For each kitten, $i$ and each person $j$ there is a cost $c_{ij}$. We would like to minimize the total cost of getting all the kittens adopted. There is also a set of constraints: each person $j$ is able to adopt no more than $u_j$ kittens. Without the constraints the problem is easy; each kitten $i$ goes with the person $j$ for which $c_{ij}$ is minimal. With the constraints is there an efficient algorithm for this problem or is it NP-hard?
Asked By : Wandering Logic
Answered By : Chao Xu
This is the min-cost max-flow problem. Consider a graph $G=(Acup Bcup {s,t},E)$, where $A$ is the set of kittens, $B$ is the set of people. Let $C:Eto mathbb{R}^+$ be the capacity of the edges, and $c:Eto mathbb{R^+}$ be the cost of an edge. We make sure that
- There is an edge between $a_i,b_j$, where $a_iin A$ and $b_jin B$, and $C(a_i,b_j)=1$, $c(a_i,b_j)=c_{i,j}$.
- There is an edge between $s$ and $a_iin A$, and $C(s,a_i)=1$, $c(s,a_i)=0$.
- There is an edge between $b_jin B$ and $t$, and $C(b_j,t)=u_j$, $c(b_j,t)=0$.
If the max flow is $M$, then we know there exist a solution. You can construct a min-cost solution from the min-cost max-flow.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18051 3.2K people like this
