## Saturday, June 25, 2016

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

Problem:

Solution:

Question 1

We had a lot of notations, but after we understand all the notations, this one is easy.

When $i = 1$, the left hand side is $w(P_0)$, $P_0$ is simply $V$, the set of all vertexes. $w(P_0)$ is the sum of all edge weights that cross partition. But there is no partitioning yet. So the left hand side is simply 0.

The right hand side is $\sum_{j=1}^{i-1}(w(\Gamma_j))$, the sum is simply empty and therefore it is also 0.

So we have $w(P_0) = 0 \le 0 = \sum_{j=1}^{i-1}(w(\Gamma_j))$

Question 2

In every iteration, we break a graph into two, so we have 1 graph in the 0th iteration, 2 graphs in the 1st iteration, and so on. Therefore, for $i \ge 2$, we have $i - 1$ graph in the $i - 2$ iteration.

Question 3

In $P_{i-2}$, we have $i - 1$ graphs. In $\Gamma$, we have $i$ graphs. Suppose we pick a part in $\Gamma$, pick one terminal in it, and dump the corresponding partition in $P_{i-2}$, eventually, we will have problem finding the corresponding graph (you can at most dump $i - 1$ times in $P_{i-2}$, but we have to dump $i$ times in $\Gamma$). In that moment, we found the pair of terminal that is separated in $\Gamma$ but not in $P_{i-2}$.

Question 4

Notice that $B \cap \Gamma_h$ and $B \backslash \Gamma_h$ is a cut of B. The algorithm picks the best minimum cut out of all possible cuts, so we have the cost of the best possible cut is less than the cost of the particular cut. In other words

$w(P_{i-1}) - w(P_{i-2}) = cost(\text{best possible cut}) \le cost(B \cap \Gamma_h$ and $B \backslash \Gamma_h)$

Question 5

In the above, we know that $w(P_{i-1}) - w(P_{i-2}) = cost(\text{best possible cut}) \le cost(B \cap \Gamma_h$ and $B \backslash \Gamma_h)$.

We also know that $cost(B \cap \Gamma_h$ and $B \backslash \Gamma_h) \le w(\Gamma_h)$.

So we take the sum of $w(P_{i-1}) - w(P_{i-2}) \le w(\Gamma_h)$ with the inductive hypothesis, we get the inequality we wanted and therefore we proved the lemma by induction.

Question 6

By the lecture, we know $\sum w(\Gamma) <2 OPT$, so we have a 2-approximation algorithm.

Question 7

At the end of the algorithm, the while loop terminates, there are $k$ graphs. Each of the graph has at least one terminal by construction. There are only $k$ terminals. So we have one terminal in each of the graph, therefore the solution is a valid multi-way cut.

Question 8

The obvious way to find a minimum cut separating any two vertices is to try all pairs. Assuming there are $p$ terminals in $G_i$, the cost would be $\frac{p(p-1)}{2}T$.

Question 9

There are at most $k$ graph in $P$. Each graph has at most $n - k$ vertices.

Question 10

The worst case of the algorithm happens when in every iteration, we isolated exactly one terminal as a graph and add to $P$. The first iteration would need $\frac{k(k-1)}{2} T$ , the second iteration would need $\frac{(k-1)(k-2)}{2} T$, and so on.

The overall complexity is $\sum\limits_{i = 1}^{k-1} \frac{i(i+1)}{2}T$

We can simplify the sum as

$\sum\limits_{i = 1}^{k-1} \frac{i(i+1)}{2}T$
$= \frac{T}{2}\sum\limits_{i = 1}^{k-1} i(i+1)$
$= \frac{T}{2}\sum\limits_{i = 1}^{k-1} (i^2 + i)$
$= \frac{T}{2}(\frac{(k-1)(k)(2(k-1)+1)}{6} + \frac{(k-1)(k)}{2})$
$= \frac{T}{2}(\frac{(k-1)(k)(2k-1)}{6} + \frac{3(k-1)(k)}{6})$
$= \frac{T}{2}(\frac{(k-1)(k)(2k+2)}{6})$
$= \frac{T}{2}(\frac{(k-1)(k)(k+1)}{3})$
$= \frac{(k-1)(k)(k+1)T}{6}$

If we like, we can also express that as $O(k^3T)$.