.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: [email protected]
![[DVI]](../gif/DVI.gif)
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)