| Article ID: | iaor2002899 |
| Country: | Germany |
| Volume: | 90 |
| Issue: | 1 |
| Start Page Number: | 101 |
| End Page Number: | 111 |
| Publication Date: | Jan 2001 |
| Journal: | Mathematical Programming |
| Authors: | Ye Y. |
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.