The following is taken fromDesign of Approximation Algorithms by Williamson and Shmoys available athttps://www.designofapproxalgs.com/book.pdf
Exercise 4.6 Let$G = (A, B, E)$ be a bipartite graph; that is, each edge$(i, j) \in E$ has$i \in A$ and$j \in B$. Assume$|A| \leq |B|$and that we are given nonnegative costs$c_{ij} \geq 0$ for each edge$(i, j) \in E$. Acomplete matching of$A$ is a subset of edges$M> \subset E$ such that each vertex in$A$ has exactly one edge of$M$incident on it, and each vertex in$B$ hasat most one edge of$M$incident on it. We wish to find a minimum-cost complete matching.
We can formulate this as an Integer Program with$x_{ij} \in \{ 0, 1> \}$ for each edge$(i, j) \in E$, where$x_{ij} = 1$ if$(i, j)$ inthe matching,$0$ otherwise. Then the program is
$$\text {min} \sum_{(i, j) \in E} c_{ij}x_{ij}$$$$\text {subject to:}$$$$\sum_{j \in B: (i, j) \in E} x_{ij} = 1 \forall i\in A$$$$\sum_{i \in A: (i, j) \in E} x_{ij} \leq 1 \forall j \in B$$$$x_{ij} \in \{ 0, 1\} \forall (i, j) \in E$$
Consider the LP relaxation where we replace the last constraint with$x_{ij} \geq 0$.
We need to show that given any fractional solution to the LPrelaxation, it's possible to find in polynomial time an integersolution that costs no more than the fractional solution.
We are given the hint that we need to modify the fractions repeatedlysuch that the solution stays feasible and the cost doesn't increase,and one of the fractions becomes$0$ or$1$.
The second part asks us to show that any extreme point of therelaxation is integral with$0, 1$ values.
I think the way forward is to notice that the objective is linear in$x_{ij}$, so we can find some$x_{ij}$ that is fractional. Find some fractional$x_{ik}$ and$x_{lj}$ such that$x_{ik}$ also fractional but$x_{lj}$ is zero or fractional.
If the former,$c_{ij} > c_{ik}$, increase$x_{ij}$ and decrease$x_{ik}$ till$x_{ij}$ is$1$ or$x_{ik}$ is$0$, whichever comes first. If$c_{ij} \leq c_{ik}$, do the opposite. It still satisfies all inequalities.
If the latter, we can do something similar, but this time we'll need to check if$c_{ij} > c_{ik} + c_{kj}$. If yes, increase$x_{ij}$ decreasing both. Otherwise, we can increase both, while decreasing$x_{ij}$.
I am unsure about this though. For the second part, again a bit unsure. We need to find two points such that the fractional solution lies in the middle to disprove extreme-ity. I feel like increasing/decreasing an edge by$\epsilon > 0$ would work. This would set off a chain of other increase/decrease, so what if the chain is self-contradictory, i.e. we increase one edge and later find out we should also decrease it.
Any thoughts and help are much appreciated!
- $\begingroup$What has this got to do with convex optimisation?$\endgroup$copper.hat– copper.hat2025-06-11 04:36:33 +00:00CommentedJun 11 at 4:36
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.