Abstract:

Given an undirected graph with nonnegative weight for each edge, the max cut problem is to partition its vertex set into two parts such that the total weight of crossing edges is maximized. When the optimal solution of its Service Design Package (SDP) relaxation lies in a two-dimension space, Goemans improved the approximation ratio from 0.87856... to 0.88456. Using the Gegenbauer polynomials rounding technique, we obtain an approximation curve depending on the ratio between the optimal value of the SDP relaxation and the total weight,  which has the lowest point 0.88456. We further improve the  approximation ratio curve when the ratio varies from 0.5 to 0.9044. Furthermore, we consider an important variant of the max cut problem, the max bisection problem, in which the equal cardinality constraint for the two parts in the partition is imposed. We also consider the case that the optimal solution of the SDP relaxation for the Max Bisection problem lies in a two-dimension space and obtain a 0.7091-approximation for this variant by using the aforementioned Gegenbauer polynomials rounding technique.

Key words: max cut problem, max bisection problem, approximation algorithm, semidefinite programming