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

Click for background material…

Using randomized rounding to derive greedy and Lagrangian-relaxation algorithms
Problem definition: maximum $c$ -matching. Given a graph $G=(V,E)$ with edge values $v_ e\ge 0$ and integer vertex capacities $c_ u\gt 0$ , a fractional $c$ -matching is a vector $x\in {\mathbb R}_+^ E$ such that, for each vertex $u\in V$ , $x$ meets the capacity constraint $\sum _{e\ni u} x_ e \le c_ u$ . The value of the fractional matching is $v\cdot x = \sum _ e v_ e x_ e$ . If $x$ has integer values, then $x$ is called a $c$ -matching.

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$ .

Click for proof of lemma…

Let $T$ be the number of iterations until $\tilde x$ makes some vertex constraint tight.

Each of the first $T$ iterations contributes in expectation $v\cdot x/|x|$ to the value of $\tilde x$ , so by Wald’s equation the expectation of $v\cdot \tilde x$ is at least $\textrm{E}[T] v\cdot x/|x|$ .

To finish we show $\textrm{E}[T] \ge |x|/n$ . Consider the sum of the vertex “loads” $\sum _{u\in V} \sum _{e\ni u} \tilde x_ e/c_ u$ . Using the feasibility of $x$ , in each iteration, the expected increase in the sum is

\[ \renewcommand{\mathspread }{\, \, \, }\sum _ u \sum _{e\ni u} \frac{x_ e/|x|}{c_ u} {\, \, \, {\le }\, \, \, }\sum _ u \frac{1}{|x|} {\, \, \, {=}\, \, \, }n/|x|. \]

That is, the sum increases by at most $n/|x|$ in expectation with each sample. The sum starts at zero and increases to at least 1 by time $T$ , so Wald’s equation implies $\textrm{E}[T] \ge |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.

Click for proof of lemma…

Fix any edge $e\in E$ . Let $T_ e$ be the number of iterations until $\tilde x$ makes the vertex constraint tight for one of $e$ ’s endpoints. To show $\textrm{E}[T_ e] \ge |x|/2$ , consider the sum of $e$ ’s vertex loads, $\sum _{u\in e} \sum _{e'\ni u} \tilde x_{e'}/c_ u$ . In each iteration, the expected increase in the sum is

\[ \renewcommand{\mathspread }{\, \, \, }\sum _{u\in e} \sum _{e’\ni u}\frac{x_{e’}/|x|}{c_ u} {\, \, \, {\le }\, \, \, }\sum _{u\in e} \frac{1}{|x|} {\, \, \, {=}\, \, \, }\frac{2}{|x|}. \]

The sum starts at zero and increases to at least 1 by time $T$ , so by Wald’s equation, $\textrm{E}[T_ e] \ge |x|/2$ .

Each of the first $T_ e$ iterations contributes in expectation $x_ e/|x|$ to $\tilde x_ e$ , so by Wald’s equation the expectation of $\tilde x_ e$ is at least $\textrm{E}[T_ e] x_ e/|x| \ge x_ e/2$ . The lemma follows by linearity of expectation.

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:

Click for algorithm from global analysis…

1.	Initialize $\tilde x = \mathbf0$ .
2.	Repeat until a vertex is at capacity:
3.	Choose an edge $e=(u,w) \in E$ maximizing $v_ e / (d_ u/c_ u + d_ w/c_ w)$ ; increment $\tilde x_ e$ . Here $d_ u$ is the degree of $u$ .
4.	Return $\tilde x$

Hint: Use $\renewcommand{\mathspread }{\, \, \, }v\cdot {\tilde x} + ({v\cdot x}/{n})\big (1 - \sum _{u\in V}\sum _{e\ni u} {\tilde x}_ e/c_ u\big )$ for the pessimistic estimator for the conditional expectation of the final value of $v\cdot {\tilde x}$ given the current ${\tilde x}$ . Argue that the algorithm keeps the pessimistic estimator from decreasing.

Algorithm

Finally, we show that applying the method of conditional probabilities yields the algorithm.

Click for proof of theorem…

Condition on the first $t$ random samples. We need a pessimistic estimator lower-bounding the conditional expectation of the value of the final $c$ -matching.

Following the localized analysis, fix any edge $e$ and let $T_ e$ denote the number of samples until one of $e$ ’s vertices reaches capacity. Given the current $\tilde x$ , recall that the sum of $e$ ’s vertex loads is

\[ \phi ^ t_ e~ =~ \sum _{u\in e} \sum _{e’\ni u} \frac{\tilde x_{e’}}{c_ u}. \]

Recall that in expectation, this sum increases by at most $2/|x|$ with each sample, and that the sum is at least 1 at time $T_ e$ (when one of $e$ ’s vertices is at capacity). So, by Wald’s equation, the expected number of additional samples until one of $e$ ’s vertices reaches capacity is at least $(1-\phi _ t)|x|/2$ . Until that happens, each sample has a chance of $x_ e/|x|$ of choosing $e$ . By Wald’s equation, the expected further increase in $v_ e \tilde x_ e$ is therefore at least $v_ e x_ e(1-\phi _ e^ t)/2$ .

Let $\tilde E$ denote the edges whose endpoints are both not yet at capacity. Summing over these edges, the expectation of the value of the final matching, given the current matching $\tilde x$ , is at least

\[ \Phi _ t ~ =~ \renewcommand{\mathspread }{\, \, \, }v\cdot \tilde x ~ +~ \sum _{e\in \tilde E} \frac{v_ e \tilde x_ e}{2} (1-\phi ^ t_ e). \]

If the algorithm next increments $\tilde x_{\tilde e}$ for a given edge $\tilde e\in \tilde E$ , this increases the vertex load of each vertex $u \in \tilde e$ by $1/c_{u}$ . For each edge $e\in \tilde E$ incident to $u$ , this also decreases the sum $\phi _ e^ t$ by $1/c_{u}$ . Thus, letting $\tilde E(u)$ denote the edges in $\tilde E$ incident to $u$ , the increase in the pessimistic estimator is

\[ \Phi _{t+1}-\Phi _ t ~ \ge ~ v_{\tilde e} – \frac{1}{2}\sum _{u\in \tilde e} \sum _{e\in \tilde E(u)} \frac{x_ e v_ e}{c_ u}. \]

(Note that edges may drop out of $\tilde E$ , but this only increases the pessimistic estimator, as $\phi ^ t_ e \ge 1$ for such edges.) Since the algorithm chooses $\tilde e$ to maximize $v_ e$ among $e\in \tilde E$ , the right-hand side above is at least

\[ v_{\tilde e} – \frac{v_{\tilde e}}{2} \sum _{u\in \tilde e} \sum _{e\in \tilde E(u)} \frac{x_ e}{c_ u} ~ \ge ~ v_{\tilde e} – \frac{v_{\tilde e}}{2} \sum _{u\in \tilde e} 1 ~ =~ 0. \]

(The inequality above follows from the feasibility of $x$ , in particular $\sum _{e\ni u} x_ e \le c_ u$ .)

Thus, the algorithm keeps the pessimistic estimator $\Phi _ t$ above $v\cdot x/2$ . Finally, at termination, note that $v\cdot \tilde x = \Phi _ T$ , because $\tilde E = \emptyset$ .

${\rm H}(d)$ -approximation ratio for Set Cover (localized)

Notes on algorithms

Lecture notes on algorithms

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

Algorithm

A weak global analysis

Localizing the analysis

Method of conditional probabilities

Algorithm

Related