[Solved]: Complexity of the Kitten Adoption problem

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=(A\cup B\cup \{s,t\},E)$, where $A$ is the set of kittens, $B$ is the set of people.

Let $C:E\to \mathbb{R}^+$ be the capacity of the edges, and $c:E\to \mathbb{R^+}$ be the cost of an edge. We make sure that

1. There is an edge between $a_i,b_j$, where $a_i\in A$ and $b_j\in B$, and $C(a_i,b_j)=1$, $c(a_i,b_j)=c_{i,j}$.
2. There is an edge between $s$ and $a_i\in A$, and $C(s,a_i)=1$, $c(s,a_i)=0$.
3. There is an edge between $b_j\in 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

 Download Related Notes/Documents