We can define a greedy algorithm that achieves a $1 / 2$-approximation: For a graph $G=(V, E)$ with $V=\{1, \ldots, n\}$, define $E_i=\{(k, i) \in E: k<i\}$. Initially, let $V_1=\{1\}$ and $V_2=\emptyset$. Then, for each $i$ from 2 to $n$, add $i$ to either $V_1$ or $V_2$ so that number of edges in $E_i$ that are on the cut is maximised. We claim that this heuristic achieves 1/2-approximation. ###### Proof: Let $C$ be the cut obtained by the algorithm. The disjoint sets $E_1, E_2, \ldots, E_n$ partition $E$. So, $|E|=\Sigma_i E_i$. For each $i \in V$, let $E_i^{\prime}=E_i \cap C$. Then, $C=\bigcup_i E_i^{\prime}$. As sets $E_i$ are disjoint, the sets $E_i^{\prime}$ are also disjoint. Thus, $|C|=\Sigma_i\left|E_i^{\prime}\right|$. The main observation is that for each $i \in V$, we have $E_i^{\prime} \geq E_i / 2$. We conclude that $|C| \geq|E| / 2$. As the size of maximum cut $\left|C^*\right| \leq|E|,|C| \geq(1 / 2)\left|C^*\right|$. # References 1. CS 810: Introduction to Complexity Theory 04/01/03 Lecture 19: Randomized Algorithms: MAXCUT