# 1/2 Approximation to MAX-DICUT by rounding a linear program

Consider a graph $$G=(V, A, w)$$, where each arc $$(u,v)\in A$$ has a non negative weight $$w_{u,v} \in \mathbb{R}^+$$, partition $$V$$ into $$U$$ and $$W$$, $$W=V-U$$ such that $$\sum_{(i,j)\in A} w_{i,j}z_{i,j}$$ where $$z_{i,j} = [[i\in U \land j \in W]]$$.

By getting a randomized cut we have a 1/4 approximation:

\begin{align} \mathbb{E}\left[\sum_{(i,j)\in A} w_{i,j} z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j}\mathbb{E}\left[z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j} \Pr(i\in U \text{ and } j\in W) \geq \frac{1}{4} OPT \end{align}

We can instead solve an integer program to get an exact solution. Consider a randomized algorithm that solves the linear relaxation of the integer program below and puts each vertex $$i$$ in $$U$$ with probability $$1/4+x_i/2$$.

\begin{align} \text{maximize } &\sum_{(i,j)\in A} w_{i,j} z_{i,j}\\ \text{subject to }& z_{i,j} \leq x_{i} &\ \forall (i,j) \in A\\ & z_{i,j} \leq 1- x_{j} &\forall (i,j) \in A\\ & x_{i}\in\left\{0,1\right\} &\forall i \in V\\ & 0\leq z_{i,j} \leq 1 &\forall (i,j) \in A\\ \end{align}

We can relax the integer program to a linear program by relaxing $$x_{i}\in\left\{0,1\right\}$$ to $$x_{i}\in[0,1]$$ for all $$i \in V$$.

\begin{align} \mathbb{E}\left[\sum_{(i,j)\in A} w_{i,j} z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j}\mathbb{E}\left[z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j} \Pr(i\in U \text{ and } j\in W) = \sum_{(i,j)\in A}w_{i,j}(\frac{1}{4}+\frac{x_i}{2})\left[1-(\frac{1}{4}+\frac{x_j}{2})\right] \end{align}

I have trouble however going further and showing that this is a 1/2 approximation though.

The constraints force $$z_{ij} = \min(x_i,1-x_j)$$. Therefore you have to show that $$\left(\frac{1}{4} + \frac{x_i}{2}\right) \left(\frac{1}{4} + \frac{1-x_j}{2}\right) \geq \frac{1}{2} \min(x_i,1-x_j).$$ By symmetry, we can assume that $$x_i \leq 1 - x_j$$, and so we have to show that $$\left(\frac{1}{4} + \frac{x_i}{2}\right)^2 \geq \frac{x_i}{2}.$$ You can check that this holds for all $$x_i$$. Equality holds when $$x_i = 1-x_j = 1/2$$, showing that the approximation ratio $$1/2$$ is tight (for the analysis).