|
|||||
|
|
| APPOXIMATION ALGORITHM FOR MAX—BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION | |
| 引用本文： | Da-chuanXu Ji-yeHan. APPOXIMATION ALGORITHM FOR MAX—BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION[J]. 计算数学(英文版), 2003, 21(3): 357-366 |
| 作者姓名： | Da-chuanXu Ji-yeHan |
| 作者单位： | InstituteofAppliedMathematics,AcademyofMathematicsandSystemSciences,ChineseAcademyofSciences,Beijing100080,China |
| 摘 要： | Using outward rotations,we obtain an approximation algorithm for Max-Bisection problem,i.e.,Partitioning the vertices of an unirected 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. |
| 关 键 词： | 近似算法 最大二等分问题 正半定规划松弛 外向旋转 无向图 基数性 |
Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation |
|
| Da-Chuan Xu , Ji-Ye Han. Approximation Algorithm for Max-Bisection Problem with the Positive Semidefinite Relaxation[J]. Journal of Computational Mathematics, 2003, 21(3): 357-366 | |
| Authors: | Da-Chuan Xu & Ji-Ye Han |
| Abstract: | 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. |
| Keywords: | Approximation algorithm Max-Bisection problem Semidefinite programming Approximation ratio. |
| 本文献已被 维普 等数据库收录！ | |
| 点击此处可从《计算数学(英文版)》浏览原始摘要信息 | |