# greedy algorithm for Maximum directed cut [closed]

Maximum directed cut: Given a directed graph $G = (V, E)$ with nonnegative edge costs, find a subset $S \subseteq V$ to maximize the total cost of edges out of $S$: $\mathrm{cost}( \{ (u \to v) \mid u \in S \text{ and } v \in \bar{S} \})$.

I am trying to come up with a greedy algorithm for Maximum directed cut with factor 1/4.

• What have you tried? Where did you get stuck? We want to help you understand the issues at hand, not do your homework for you. – Tom van der Zanden Oct 15 '15 at 8:09
• considers vertexes in non-increasing order with respect to the sum of the cost of out edge/out-degree. when two vertexes have same ratio choose the vertex have lower in-degree. when a vertex is chosen all the vertexes are connected with it are removed.repeat until all vertexes are chosen or deleted. – Z.S.CS Oct 15 '15 at 8:29
• I do not know this algorithm is right. – Z.S.CS Oct 15 '15 at 8:34
• Have you tried this algorithm? Does it seem to work? Have you tried proving that it works? – Yuval Filmus Oct 15 '15 at 9:56

The starting point is the trivial random algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $1/4$ approximation.
We can derandomize this algorithm using the method of conditional expectations. Arrange the points in order: $1,\ldots,n$. At step $i$, we know which of $1,\ldots,i-1$ are in $S$ and which are in $\bar{S}$. If we put $i \in S$, then we can compute the expected cost of the output given that all further choices are made randomly; and we can do the same if we put $i \in \bar{S}$. One of these choices cuts at least $1/4$ of the edges (in terms of weight), and this is the one we choose.
We can further optimize this algorithm. Consider the following two expressions: $$A = \sum_{\substack{j<i\\j\in\bar{S}}} w_{ij} + \frac{1}{2} \sum_{j>i} w_{ij}, \\ B = \sum_{\substack{j<i\\j\in S}} w_{ji} + \frac{1}{2} \sum_{j>i} w_{ji}.$$ (Here $w_{ij}$ is the cost of the edge from $i$ to $j$.) If $A>B$ then the derandomized algorithm puts $i$ in $S$, whereas if $A<B$ it puts $i$ in $\bar{S}$ (if $A=B$ it doesn't matter). We can perhaps think of this algorithm as a greedy algorithm.
As an aside, the so-called double greedy algorithm gives a $1/2$ approximation algorithm. The greedy algorithm you suggest in the comments is good in combination with the random algorithm: if you run both and choose the better solution, you get a $2/5$ approximation (see Feige's paper). The semidefinite relaxation gives the (probably) optimal approximation ratio, which is roughly 0.874.