MIT 6.1220 — Lecture 16

Approximation Algorithms (Part II)

Problem. (Weighted Vertex Cover) Given a graph $G$ , find a minimum-weight vertex cover.

Solution. (Weighted Vertex Cover) Write the appropriate minimization LP: the variables are $\{x_v\}_{v \in V}$ , the constraints are $x_v \in [0, 1]$ and $x_u + x_v \geq 1$ for each $(u, v) \in E$ , and the quantity to be minimized is $\sum_{v \in V} w(v) \cdot x_v$ .

Find the optimal solution, then round it: output $S = \{v \in V: x_v^* \geq 0.5\}$ .

Proof: Say $x^*$ is the LP optimal we find, $x$ is the rounded solution, and $S^*$ is the vertex-cover optimal.

The proof is in two inequalities. The former holds because rounding incurs at most a factor-of-two increase. The latter holds because all ILP solutions are LP solutions.

\sum_{v \in V} w(v) \cdot x_v \leq 2 \cdot \sum_{v \in V} w(v) \cdot x_v^* \leq 2 \cdot \sum_{v \in S^*} w(v).

You should show $x$ is a valid solution to begin with. You can also show $\alpha = 2$ is tight. $\blacksquare$

Problem. (Set Cover) Given subsets $S_1, \dots, S_n \subseteq \mathcal{U}$ , find a cover of $\mathcal{U}$ using as few subsets as possible.

Solution. (Set Cover) Greedily pick sets covering the most uncovered elements. This is an $O(\log |\mathcal{U}|)$ -approximation algorithm—for the same reasons as our bad Vertex Cover approximation algorithm!

(The bad Vertex Cover approximation algorithm never used the fact that edges connect two vertices…)

It turns out that if $\textbf{P} \neq \textbf{NP}$ , then we cannot do better. All of this is true for the weighted case, too.

Problem. (Clique) Find a maximum clique in a graph $G$ .

Solution. (Clique) Partition $V$ into $\frac{n}{\log n}$ subsets $\{G_i\}$ of size $\log n$ . For each subset $G_i$ of size $\log n$ , brute-force through every subset of $G_i$ to find the maximum clique in $G_i$ . Output the largest clique you found.

This is an $\left(\frac{n}{\log n}\right)$ -approximation. Obviously. And this is tight. Obviously.

It turns out that we can't do better.

Remark. Recall that Clique reduces to Vertex-Cover very easily. And Vertex-Cover has a $2$ -approximation algorithm. Think about that.

Problem. (Max-3-SAT) Given a $3$ -CNF formula, maximize the number of satisfied clauses.

Assume each clause has three distinct variables, for simplicity.

Solution. (Max-3-SAT) If you output an assignment at random, you get an $\frac{8}{7}$ -approximation in expectation.

To guarantee an $\frac{8}{7}$ -approximation, assign the variables $\{x_i\}_{i = 1}^n$ one at a time, at each point assigning $x_i$ so that the conditional expected number of clauses satisfied (assuming $\{x_{i + 1}, x_{i + 2}, \dots\}$ are assigned randomly) is largest.

You can prove inductively that this will yield an $\frac{8}{7}$ -approximation. $\blacksquare$

And, again, we can't do better.