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.

  • 2
    $\begingroup$ 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. $\endgroup$ Oct 15, 2015 at 8:09
  • $\begingroup$ 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. $\endgroup$
    – Z.S.CS
    Oct 15, 2015 at 8:29
  • $\begingroup$ I do not know this algorithm is right. $\endgroup$
    – Z.S.CS
    Oct 15, 2015 at 8:34
  • 1
    $\begingroup$ Have you tried this algorithm? Does it seem to work? Have you tried proving that it works? $\endgroup$ Oct 15, 2015 at 9:56

1 Answer 1


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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.