A 2-approximation for maximum weight c-matching, illustrating localization.
Algorithm
The algorithm below is a 2-approximation algorithm.
input: Graph G=(V,E) with edge values v and integer vertex capacities c | |
output: c-matching \tilde x | |
1. | Initialize \tilde x =\mathbf0. |
2. | Repeat until every edge has an endpoint at capacity: |
3. | Among edges with no such endpoint, choose e maximizing v_ e; increment \tilde x_ e. |
4. | Return \tilde x. |
This problem generalizes the LP dual of weighted Vertex Cover. The algorithm implicitly produces a 2-approximate (integer) solution for that problem.
To prove the theorem we’ll apply the method of conditional probabilities to the following rounding scheme:
Initialize \tilde x =\mathbf0. Repeat until every edge has an endpoint at capacity: choose an edge e from distribution x/|x| and increment \tilde x_ e unless one of e’s endpoints is at capacity. Return \tilde x.
A weak global analysis
We start with a weak “global” analysis of the rounding scheme. Let n be the number of vertices.
The expected value of the c-matching \tilde x is at least v\cdot x/n.
Localizing the analysis
We localize the analysis to improve the approximation ratio from 1/n to 1/2.
The expected value of the c-matching is at least v\cdot x/2.
To prove this lemma, for each edge e\in E, we apply the previous lemma to the “local” subproblem for e formed by e and edges that share an endpoint with e, and with modified objective function v’\cdot x \doteq x_ e. This gives \textrm{E}[\tilde x_ e] \ge x_ e/2. Linearity of expectation then implies the desired result.
Method of conditional probabilities
Next we apply the method of conditional probabilities to the local analysis.
As an exercise, the reader may wish to first try this for the global analysis:
Algorithm
Finally, we show that applying the method of conditional probabilities yields the algorithm.