Not approximable within 1.0624 .
Admits a PTAS if
Variation in which the degree of G is bounded by a constant B for
is still APX-complete  and .
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 
and admits a PTAS for dense instances 
and for metric weights .
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
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.431
. Admits a PTAS for some classes of weighted dense instances of
MAXIMUM BISECTION .
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