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)

No comments :

Post a Comment