14
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

This is the minimum weight perfect matching problem which is polynomial. Consider the complete bipartite graph $(L , R , E)$, in which $L$ contains a node $l_i$ for each kitten $i$, $R$ consists of $u_j$ copies of the node $r_{j}$ for each person $j$, and edges $e_{ij} \in E$ between $l_i$ and each copy of $r_{j}$, with weights $c_{ij}$.

We know that $|L| \leq |R|$, otherwise not all kittens can be assigned to persons.

Since perfect matching must match all the nodes, we need to add dummy nodes to $L$ (to get $|L| = |R|$) and connect them with zero weight edges to all the nodes in $R$.

$\endgroup$
2
$\begingroup$

Possibly of interest is the observation that one can reduce Partition to a variant of this problem. Given is an instance of Partition with elements $\{x_1,\dots,x_q\}$ with $q$ even from which we have to choose a subset $S \subseteq \{1,\dots,q\}$ with $|S|=q/2$ such that $\sum_{i\in S} x_i = \sum_{i\not\in S} x_i = K$. (Note that the requirement to choose exactly half the elements is not the usual form but this form is still NP-hard.) Let each kitten be an element of the set; let there be two people; let the weights be $c_{i1} = x_i$ and $c_{i2} = -x_i$; let $u_1 = u_2 = q/2$. Then this instance of Kitten Adoption has a maximum of $0$ iff the instance of Partition has a solution.

If the costs in Kitten Adoption are meant to always be positive then one can just add a large enough constant $C$ to all weights to ensure they are the right sign, when the required threshold is $Cq$ instead of 0.

I am not sure what this says about the complexity of the original problem, but given the often-seen "one of minimize/maximize is NP-hard, the other is in P" setup for combinatorial optimization problems, I would start looking for an efficient algorithm.

$\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.