A .699-approximation algorithm for Max-Bisection |
| |
| Authors: | Yinyu Ye |
| |
| Affiliation: | (1) Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, Iowa 52242, USA., US |
| |
| Abstract: | 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. Received: October 1999 / Accepted: July 2000?Published online January 17, 2001 |
| |
| Keywords: | : graph bisection – polynomial-time approximation algorithm – semidefinite programming |
| 本文献已被 SpringerLink 等数据库收录！ |
|
