.602 Approximation of the Complement of Min-Bisection

Yinyu Ye and Jiawei Zhang

We consider the complement of the graph min-bisection problem, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of non-crossing edges. We prove that a mixed semidefinite relaxation and simple randomization technique yield a .602 approximation for the complement of the min-bisection. The previous best-known results for this problem is .5 using a simple randomization technique and .48 using the semidefinite relaxation.

Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, Iowa 52242.

Contact: yinyu-ye@uiowa.edu