Next: MAXIMUM K-CUT
Up: Cuts and Connectivity
Previous: MINIMUM CROSSING NUMBER
  Index
- INSTANCE:
Directed graph
.
- SOLUTION:
A partition of V into disjoint sets V1 and V2.
- MEASURE:
The cardinality of the cut, i.e., the number of arcs with one end point
in V1 and one endpoint in V2.
- Good News:
Approximable within 1.165 [143].
- Bad News:
APX-complete [371].
- Comment:
Not approximable within 1.083 [226].
Admits a PTAS if
[37].
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 [120].
Viggo Kann
1999-04-22