# Maximum cut using a 1/2 approximation greedy algorithm

I have the following greedy algorithm for max cut problem:

1. Initialization: $A \leftarrow \{v_1\}$ , $B \leftarrow \{v_2\}$
2. For $v \in V − \{v_1, v_2\}$ do:

if $d(v,A) \geq d(v,B)$ then $B \leftarrow B \cup \{v\}$,

else $A \leftarrow A \cup \{v\}$.

3. Output $A$ and $B$.

Here, $v_1$ and $v_2$ are arbitrary vertices in $G$ and $d(v,A)$ denotes the number of edges between vertex $v$ and set $A \subset V$.

To show that this is a factor 1/2 approximation algorithm, I used the upper bound that $opt \leq |E|$ and internal_degree(v) and external_degree(v).

But there is a problem, I can not say that when the algorithm terminates, we have external_degree(v) $\geq$ internal_degree(v) for all v (there is a counterexample) , of course since each vertex is check once so time complexity is O(n).

Is there any other way to show this factor?

Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the number of those edges that are cut by the algorithm. Step 2 ensures that $C_v \geq N_v/2$ (this clearly holds for $v = v_2$ as well). Therefore $\sum_v C_v \geq \sum_v N_v/2$. Finally, notice that $\sum_v N_v$ is the number of edges in the graph, and $\sum_v C_v$ is the size of the cut produced by the algorithm.
Here is a sketch of another proof. At any point in time, define the score of an edge $(u,v)$ as follows:
• If $u,v \in A$ or $u,v \in B$, the score is 0.
• If $u \in A$ and $v \in B$ or vice versa, the score is 1.