Comment:
Not approximable within 1.0624 [226].
Admits a PTAS if
[37].
Variation in which the degree of G is bounded by a constant B for
is still APX-complete [371] and [9].
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]
and admits a PTAS for dense instances [150]
and for metric weights [151].
Variation in which some pairs of vertices are restricted to be on the
same side (or on different sides) is still approximable within 1.138
[186].
MAXIMUM BISECTION, the weighted problem with the additional
constraint that the partition must cut the graph into halves of the
same size, is approximable within 1.54
[164] and [347].
MINIMUM BISECTION, the problem where the partition must cut the graph
into halves of the same size and the number of edges between them is to be
minimized, admits a PTAS if the degree of each vertex is
[37].