APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

作     者：Da-chuan Xu Ji-ye Han(Institute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academyof Sciences, Beijing 100080, China) 

作者机构：Institute of Applied Mathematics Academy of Mathematics and System Sciences Chinese Academy of Sciences 北京 100080 

出 版 物：《Journal of Computational Mathematics》 (计算数学（英文）)

年 卷 期：2003年第21卷第3期

页      面：357-366页

核心收录：

学科分类：07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：Research partly supported by Chinese NSF grant 19731001 and National 973 Information Technology and High-Performance Software Program of China with grant No.G1998030401.The first author gratefully acknowledges the support of K.C.Wong Education Foundat 

主　　题：Approximation algorithm Max-Bisection problem Semidefinite programming Approximation ratio. 

摘      要：Using outward rotations, we obtain an approximation algorithm for Max-Bisection problem, i.e., partitioning the vertices of an undirected graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. In many interesting cases, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming.