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 } &amp;\sum_{(i,j)\in A} w_{i,j} z_{i,j}\\
\text{subject to }&amp; z_{i,j} \leq x_{i} &amp;\ \forall (i,j) \in A\\
&amp; z_{i,j} \leq 1- x_{j}                &amp;\forall (i,j) \in A\\
&amp; x_{i}\in\left\{0,1\right\}  &amp;\forall i \in V\\
&amp; 0\leq z_{i,j} \leq 1 &amp;\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).