Maximum c-Matching / 2-approximation (local analysis; weighted)

A 2-approximation for maximum weight c-matching, illustrating localization.

 



Algorithm

Theorem.

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.
Remark:

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.

Lemma (global analysis).

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.

Lemma (local analysis).

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.

MathJax is loading, equations are not yet displayed...