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

| cite | improve this answer | |

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