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: [email protected]