At the end of section 12.4 in the Local Search chapter from Kleinberg-Tardos's book "Algorithm Design" we are told that we can bound the running time of a proposed Maximum-Cut approximation algorithm via using "big-improvement-flips". The goal here is to use these flips to then place a bound on the running time of our approximation algorithm, but I have yet to understand how to prove statement (1) below.

A node flip is a big-improvement-flip if it improves the cut value by at least $\frac{2\epsilon}{n}w(A,B)$ where $n=\vert V \vert$ and $\epsilon > 0$.

We are given 12.6 as a result in the book (12.6 refers to the statement number in the book):

(1) Let $(A,B)$ be a partition such that no big-improvement-flip is possible. Let $(A^*,B^*)$ be a globally optimal partition. Then $(2+\epsilon)w(A,B)\geq w(A^*,B^*)$.

The claim is that by simply adding the term $\frac{2\epsilon}{n}w(A,B)$ to each inequality in the original proof, we can prove this. For original proof see slide 22 at this link, slides preceding slide 22 also describe the proposed approximation algorithm which allows us to find a local optimum by moving from a state $S$ to a state $S^*$ if and only if moving a vertex from one partition to the other increases the value of the cut: Princeton Kleinberg-Tardos lecture slides.

I had some difficulty simply adding the term and moving through the proof from beginning to end as Kleinberg-Tardos proposed. This has been very frustrating and I just want to prove to myself that that statement (1) holds.

My proof attempt:

For any node $u \in A$, we must have

$$\sum_{v\in A} w_{uv} \leq \sum_{v \in B} w_{uv} + \frac{2\epsilon}{n}w(A,B).$$

By summing the inequalities for each pair of vertices with both ends in $A$ and each pair of vertices with one end in $A$ and the other in $B$ we get

$$2 \sum_{\{u,v\}\subseteq A} w_{uv} \leq \sum_{u\in A, v \in B} w_{uv} + 2\epsilon w(A,B) = w(A,B) + 2\epsilon w(A,B).$$

*Note on above step: Since at most $n-1$ vertices are in $A$ we have on the RHS of the inequality $\frac{2\epsilon}{n}w(A,B) \leq (n-1)\frac{2\epsilon}{n}w(A,B) \leq n\frac{2\epsilon}{n}w(A,B) \leq 2\epsilon w(A,B)$

A similar argument follows for any $u \in B$ and hence

$$2 \sum_{\{u,v\}\subseteq B} w_{uv} \leq \sum_{u\in A, v \in B} w_{uv} + 2\epsilon w(A,B) = w(A,B) + 2\epsilon w(A,B).$$

Adding these inequalities gives

$$2 \sum_{\{u,v\}\subseteq A} w_{uv} + 2 \sum_{\{u,v\}\subseteq B} w_{uv} \leq 2w(A,B) + 4\epsilon w(A,B)$$ $$\sum_{\{u,v\}\subseteq A} w_{uv} + \sum_{\{u,v\}\subseteq B} w_{uv} \leq w(A,B) + 2\epsilon w(A,B)$$

At this point I would like to add $w(A,B)$ to both sides and conclude that $W = \sum_e w_e$ is now equal to the LHS (since the LHS now equals the sum total weight of all edges) and then have the RHS be equal to $2w(A,B) + \epsilon w(A,B) \Rightarrow (2+\epsilon)w(A,B) \geq w(A^*, B^*)$, but the bound I am getting is $2w(A,B) + 2\epsilon w(A,B) \Rightarrow w(A,B)(2+2\epsilon)$.

What am I missing here? I seem to be double counting the term $2\epsilon w(A,B)$.

  • $\begingroup$ The trivial bound, obtained by moving all the vertices in $A^*\Delta A$, yields $w(A^*,B^*)\le w(A,B)+|A^* \Delta A|\frac{2\epsilon}{n}w(A,B)\le w(A,B)+2\epsilon w(A,B) = (1+2\epsilon)w(A,B)$. If $\epsilon > 1$ then the bound stated in your lemma is tighter, while this seems tight already. Given $A,B$, I can choose the weights such that any vertex removed from $A$ will add $\frac{2\epsilon}{n} w(A,B)$ to the weight of the cut. $\endgroup$ – Ariel Nov 21 '17 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.