patternMinor
Find perfect matching whose weight is minimal, in polynomial time
Viewed 0 times
whosepolynomialperfectweighttimefindminimalmatching
Problem
Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ is a complete graph (else give weight $\infty$ to non-existing edges).
Giving a variable $x_{i,j}$ for each $a_i\in A$ and $b_j\in B$, I wrote the following IP:
$$ \min{\Sigma_{i,j} w(a_i,b_j)\cdot x_{i,j}} $$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$subject to $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Sigma_{j} x_{i,j}=1$ (for each $a_i\in A$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, \Sigma_{i} x_{i,j}\leq 1$ (for each $b_j\in B$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, x_{i,j}\in \{ 0,1 \}$
Assuming I have the IP solution, it's obvious how to construct a min weight matching.
The only problem is that solving an IP problem is NP-Hard. Thus, I wrote the following (very similar) LP:
$$ \min{\Sigma_{i,j} w(a_i,b_j)\cdot x_{i,j}} $$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$subject to $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Sigma_{j} x_{i,j}=1$ (for each $a_i\in A$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, \Sigma_{i} x_{i,j}\leq 1$ (for each $b_j\in B$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, x_{i,j}\geq 0$
I've seen a
Giving a variable $x_{i,j}$ for each $a_i\in A$ and $b_j\in B$, I wrote the following IP:
$$ \min{\Sigma_{i,j} w(a_i,b_j)\cdot x_{i,j}} $$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$subject to $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Sigma_{j} x_{i,j}=1$ (for each $a_i\in A$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, \Sigma_{i} x_{i,j}\leq 1$ (for each $b_j\in B$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, x_{i,j}\in \{ 0,1 \}$
Assuming I have the IP solution, it's obvious how to construct a min weight matching.
The only problem is that solving an IP problem is NP-Hard. Thus, I wrote the following (very similar) LP:
$$ \min{\Sigma_{i,j} w(a_i,b_j)\cdot x_{i,j}} $$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$subject to $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Sigma_{j} x_{i,j}=1$ (for each $a_i\in A$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, \Sigma_{i} x_{i,j}\leq 1$ (for each $b_j\in B$)
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, x_{i,j}\geq 0$
I've seen a
Solution
Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph.
Suppose we have a bipartite graph with weights on the edge, and we want to find a perfect matching whose total weight is as large as possible. Call this the maximum-weight perfect-matching problem. You can solve this problem as follows. Pick a large constant $C$ (sufficiently large); replace the weight $w$ on each edge with $w+C$ (i.e., add $C$ to each edge weight). Now find the maximum weight matching in the resulting graph using the Hungarian algorithm or any other algorithm for maximum weight matching. (Here the key fact we are using is that a maximum weight matching can be found in polynomial time.)
I claim that the resulting matching will be a perfect matching, if one exists. Why? Well, if a perfect matching exists, then its weight will be $Cn+\delta$, where $n$ is the number of edges in a perfect matching and $\delta$ is something bounded (it's the sum of $n$ weights from the original graph). The weight of any non-perfect matching will be at most $C(n-1)+\delta'$, where $\delta$ is something bounded (it's the sum of at most $n-1$ weights from the original graph). Suppose $C$ is at least $2n$ times the largest of the absolute values of the weights of the original graph. Then $Cn+\delta$ will always be larger than $C(n-1)+\delta'$, or in other words, any perfect matching will have greater total weight than any non-perfect matching. It follows that the Hungarian algorithm on this modified graph will find the maximum-weight perfect matching in the modified graph, and this corresponds to the maximum-weight perfect matching in the original graph (since we added the same constant to the weight of every edge).
So, there is a polynomial-time algorithm to find the perfect matching whose total weight is maximized. Given this, we can solve your problem (find the perfect matching whose total weight is minimized) by simply negating all of the edge weights.
Suppose we have a bipartite graph with weights on the edge, and we want to find a perfect matching whose total weight is as large as possible. Call this the maximum-weight perfect-matching problem. You can solve this problem as follows. Pick a large constant $C$ (sufficiently large); replace the weight $w$ on each edge with $w+C$ (i.e., add $C$ to each edge weight). Now find the maximum weight matching in the resulting graph using the Hungarian algorithm or any other algorithm for maximum weight matching. (Here the key fact we are using is that a maximum weight matching can be found in polynomial time.)
I claim that the resulting matching will be a perfect matching, if one exists. Why? Well, if a perfect matching exists, then its weight will be $Cn+\delta$, where $n$ is the number of edges in a perfect matching and $\delta$ is something bounded (it's the sum of $n$ weights from the original graph). The weight of any non-perfect matching will be at most $C(n-1)+\delta'$, where $\delta$ is something bounded (it's the sum of at most $n-1$ weights from the original graph). Suppose $C$ is at least $2n$ times the largest of the absolute values of the weights of the original graph. Then $Cn+\delta$ will always be larger than $C(n-1)+\delta'$, or in other words, any perfect matching will have greater total weight than any non-perfect matching. It follows that the Hungarian algorithm on this modified graph will find the maximum-weight perfect matching in the modified graph, and this corresponds to the maximum-weight perfect matching in the original graph (since we added the same constant to the weight of every edge).
So, there is a polynomial-time algorithm to find the perfect matching whose total weight is maximized. Given this, we can solve your problem (find the perfect matching whose total weight is minimized) by simply negating all of the edge weights.
Context
StackExchange Computer Science Q#39517, answer score: 7
Revisions (0)
No revisions yet.