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

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

# Algorithm

Theorem.

The algorithm below is a 2-approximation algorithm.

 input: Graph with edge values and integer vertex capacities output: -matching 1. Initialize . 2. Repeat until every edge has an endpoint at capacity: 3. Among edges with no such endpoint, choose maximizing ; increment . 4. Return .
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 . Repeat until every edge has an endpoint at capacity: choose an edge from distribution and increment unless one of ’s endpoints is at capacity. Return .

# A weak global analysis

We start with a weak “global” analysis of the rounding scheme. Let be the number of vertices.

Lemma (global analysis).

The expected value of the -matching is at least .

## Localizing the analysis

We localize the analysis to improve the approximation ratio from to .

Lemma (local analysis).

The expected value of the -matching is at least .

To prove this lemma, for each edge , we apply the previous lemma to the “local” subproblem for formed by and edges that share an endpoint with , and with modified objective function . This gives . 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.