Next: MAXIMUM K-CUT
Up: Cuts and Connectivity
Previous: MINIMUM CROSSING NUMBER
  Index
- INSTANCE:
Directed graph
.
- SOLUTION:
A partition of V into disjoint sets
and .
- MEASURE:
The cardinality of the cut, i.e., the number of arcs with start point
in
and endpoint in .
- Good News:
Approximable within 1.165 [154].
- Bad News:
APX-complete [393].
- Comment:
Not approximable within 1.083 [242].
Admits a PTAS if
[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].
Viggo Kann
2006-12-30