Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MAXIMUM DIRECTED CUT

• INSTANCE: Directed graph $G=\left(V,A\right)$.

• SOLUTION: A partition of V into disjoint sets $V_1$ and $V_2$.

• MEASURE: The cardinality of the cut, i.e., the number of arcs with start point in $V_1$ and endpoint in $V_2$.

  
  

• Good News: Approximable within 1.165 [154].

• Bad News: APX-complete [393].

• Comment: Not approximable within 1.083 [242]. Admits a PTAS if $\vert E\vert =\Theta(\vert V\vert^2)$ [39]. Variation in which each edge has a nonnegative weight and the objective is to maximize the total weight of the cut is as hard to approximate as the original problem [128].