A .699-Approximation Algorithm for Max-Bisection

Yinyu Ye

We present a .699-approximation algorithm for max-bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson.

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

Contact: yyye@dollar.biz.uiowa.edu