Next: MAXIMUM K-CUT
Up: Cuts and Connectivity
Previous: MINIMUM CROSSING NUMBER
A partition of V into disjoint sets
The cardinality of the cut, i.e., the number of arcs with one end point
and one endpoint in .
- Good News:
Approximable within 1.165 .
- Bad News:
Not approximable within 1.083 .
Admits a PTAS if
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 .