I've been trying to solve this problem for two days. This problem is from Vazirani's book Approximation Algorithms (pg 23).

Given an undirected graph $G = (V,E)$ with nonnegative edge costs, and an integer $k$, find a partition of $V$ into sets $S_1,\dots, S_k$ so that the total cost of edges running between these sets is maximized. Give a greedy algorithm for this problem that achieves a factor of $(1−\frac{1}{k})$. Is the analysis of your algorithm tight?

I am trying to solve it using local search as following. Initially I create $k$ empty partitions $V_1, \dots, V_k$, then divide vertices arbitrarily into $k$ parts and put each part into the partitions, so that initially each partition $V_i$ has $\frac{|V|}{k}$ vertices.

My local move runs over each partition $V_i$ and for each vertex $v \in V_i$ puts $v$ into another partition and then checks the sum of the weights of crossing edges between each partition $V_i$ and $V_j$. If this move improves (increases) the sum of the weights of the cut then we continue the local search, otherwise we reached the local maximum.

But I am not able to prove that this guarantees $OPT(1-\frac{1}{k})$. I suspect that my approach is not correct which does not result in $(1-\frac{1}{k})$-approximation. So far I could obtain the following inequality $$opt \geq (k-1)\sum{w(e)}, \text{ where } e \text{ are all noncrossing edges and } opt \text{ is the local maximum}$$

Could someone give me a right direction, or help prove that this approach indeed yields $(1-\frac{1}{k})$-approximation?

  • 1
    $\begingroup$ Start by considering the expected cost of cut edges if you assign each vertex to a $V_i$ chosen uniformly at random. (What is the chance that a given edge $(u,w)$ is cut?) Then derandomize to get a greedy algorithm. $\endgroup$ – Neal Young Dec 7 '17 at 2:03
  • $\begingroup$ @NealYoung thanks for hints. I am new to derandomization of algorithms. I've googled and found a couple of pdf files explaining derandomization. If you have any reference, tutorials explaining this concept please share it. $\endgroup$ – B.K. Dec 7 '17 at 8:44
  • $\begingroup$ algnotes.info/on/background/probabilistic-method/… $\endgroup$ – Neal Young Dec 9 '17 at 2:15

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.