I'm trying to formulate a greedy algorithm for the Max k-cut problem:

Let's have an not oriented graph $G(V,E)$, each edge $e \in E$ has its weight $w_e$. The goal of the algorithm is to divide all vertices $v\in V$ to $k$ disjunct sets $V_1,\dots,V_k$ and maximize the weight of the edges that are connecting these sets.

I have come up with the following algorithm:

  1. Take any vertex $v$ from $v\in V$ and add it into a queue $Q$.
  2. while $Q$ is not empty
    1. take the first vertex from the queue. (Let's name it $u$.)
    2. $p_i:=0$ for $i\in\{1, 2, \dots, k\}$
    3. for each neighbour $n\in \text{Neighbours}(u)$ consider the edge $\{u, n\}$.
      1. $p_i := p_i + 1$ if $n\in V_i$
    4. Add the vertex $u$ to the set $V_i$ that has the lowest $p_i$.
    5. Add all neighbours of $u$ that have not been yet assigned to any set to the queue $Q$.
  3. return $V_1, V_2, \dots, V_n$

It is basically a greedy breadth-first search algorithm, that adds each vertex to the best set based on information of the neighbours that have already been added.

Now I am trying to analyze the algorithm, if it is an $\left(1-\frac{1}{k}\right)$-approximation algorithm, but I am having hard time finding where to start.

Could someone please give me some hints on how to analyze this algorithm?

  • 1
    $\begingroup$ You use statements such as for each. Could you add indents to your pseudocode? In particular it is not clear which lines belong to the for-statement in the line 3. Also it is not clear whether for-statements in line 3 and 5 are nested. $\endgroup$ – fade2black Dec 8 '17 at 14:09
  • $\begingroup$ I have added indentation, I hope it is more understandable now. $\endgroup$ – janjaromirhorak Dec 8 '17 at 14:53
  • $\begingroup$ ...and I removed one line, that might be misleading. $\endgroup$ – janjaromirhorak Dec 8 '17 at 17:59

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.