Prove that the 2-approximation of a modified local search algorithm for max-cut is tight
Let's denote by $u_1,\ldots,u_{2n}$ and $v_1,\ldots,v_{2n}$ the nodes in the two sides of $K_{2n,2n}$ respectively. We remove the $2n$ edges $(u_1,v_1),(u_2,v_2),\ldots,(u_{2n},v_{2n})$ from $K_{2n,2n}$. You can verify the resulting graph is an example showing the approximation ratio of your algorithm is at least $2-1/n$, when the initial cut is $\left(\{u_1,\ldots,u_n,v_1,\ldots,v_n\},\{u_{n+1},\ldots,u_{2n},v_{n+1},\ldots,v_{2n}\}\right)$.