## Saturday, May 28, 2016

### Coursera Approximation Algorithms Part I - Peer Assignment 1

Problem:

Solution:

To repeat the obvious, we have the linear programming relaxation as follow:

minimize $\sum w_i x_i$
subject to $x_i + x_j \ge 1$ for all edges $(i, j)$.
$0 \le x_i \le 1$.

The particular relaxation for this approximation algorithm requires $x_i$ be an integral multiple of $\frac{1}{2}$.

Question 1:

We have $val(X) = \sum w_i x_i$, we know all the weights are 1 so it simplifies to $\sum x_i$.

Each node in $V^1$ contribute 1 to the sum, and each node in $V^{\frac{1}{2}}$ contribute $\frac{1}{2}$ to the sum, so we have $val(x) = |V^1| + \frac{1}{2}|V^{\frac{1}{2}}|$.

Question 2:

This is probably the hardest question in this assignment. For a simple case let think of this simplified scenario.

$2 = a + b$
$b \ge a$

In this case we claim that $b \ge 1$, this is obvious to argue using contradiction.

For $|V_3^{\frac{1}{2}}|$, the situation is analogous, we have $|V_3^{\frac{1}{2}}| \ge |V_2^{\frac{1}{2}}| \ge |V_1^{\frac{1}{2}}| \ge |V_0^{\frac{1}{2}}|$, so we would expect $|V_3^{\frac{1}{2}}| \ge \frac{1}{4}|V^{\frac{1}{2}}|$, but how do we go about proving it?

Again, we start with the small case, we have $d \ge c \ge b \ge a$.

$b \ge a$,
$b + b \ge a + b$
$2b \ge a + b$

so we have $b \ge \frac{1}{2}(a + b)$.

For the four variables case we simply do exactly the same idea

$d \ge a$
$d \ge b$
$d \ge c$

Sum these 3 inequalities there we get

$3d \ge a + b + c$
$4d \ge a + b + c + d$

So dividing get us the answer

$d \ge \frac{1}{4}(a + b + c + d)$.

That gives a formal proof to the expected value.

Question 3

$|V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| + |V_3^{\frac{1}{2}}| = |V^{\frac{1}{2}}|$

Multiply -1 to both side on the inequality we got above, we have

$-|V_3^{\frac{1}{2}}| \le -\frac{1}{4}|V^{\frac{1}{2}}|$

Taking the sum of the two, we get
$|V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| \le \frac{3}{4}|V^{\frac{1}{2}}|$

Question 4

The number of nodes in the final vertex cover is
$|V^1| + |V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}|$
$\le |V^1| + \frac{3}{4}|V^{\frac{1}{2}}|$
$= \frac{3}{2}|V^1| + \frac{3}{4}|V^{\frac{1}{2}}|$
$< \frac{3}{2}(|V^1| + \frac{1}{2}|V^{\frac{1}{2}}|)$
$= \frac{3}{2}(val(X))$

Question 5

Since our LP is a relaxation, we have $val(X) \le OPT$, $|V^1| + |V_0^{\frac{1}{2}}| + |V_1^{\frac{1}{2}}| + |V_2^{\frac{1}{2}}| \le \frac{3}{2}val(X) \le \frac{3}{2}OPT$, therefore we conclude it is a $\frac{3}{2}$ approximation for vertex cover (modulo the correctness, which we will show later)

Question 6

$v$ has to belong to $V^1$, for $x_u = 0$ and $x_u + x_v \ge 1$.

Question 7

We have already solved the case for $u \in V^0$, $v$ must be $V^1$.
If $u \in V^1$, then $v$ can be in any set.
If $u \in V^{\frac{1}{2}}$, then $v$ can be in either $V^1$ or $V^{\frac{1}{2}}$.

Question 8

If both node $u \in V^{\frac{1}{2}}$ and $v \in V^{\frac{1}{2}}$ are not in $S$, then the only possibility is that both of them are in $V_3^{\frac{1}{2}}$.

Question 9

But C is a colouring meaning no two nodes share an edge have the same color. So it is impossible for $(u, v)$ be an edge, $u \in V^{\frac{1}{2}}$ and $v \in V^{\frac{1}{2}}$ are not in $S$. In other words, all edges must be covered. This concludes the approximation algorithm is correct.

Question 10

All planar graphs are 4 colourable, it is the four colour theorem. Of course, trees, bipartite graphs are also 4 colourable (in fact, 2 colourable)