Approximation algorithms for MAX-BISECTION on low degree regular graphs
The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 less than or equal to k less than or equal to 8, by deriving some improved transformations from a maximum cut into