ON APPROXIMATION OF MAX n/2-UNCUT PROBLEM

作     者：XU Dachuan(Institute of Applied Mathematics, Academy of Mathematics and Systems Sciences, Chinese. Academy of Sciences, Beijing 100080, China) XU Dachuan(Institute of Applied Mathematics, Academy of Mathematics and Systems Sciences, Chinese. Academy of Sciences, Beijing 100080, China)

作者机构：Institute of Applied Mathematics Academy of Mathematics ami Systems Sciences Chinese Aeailemy of Sciences 北京 100080 

基　　金：This research is partly supported by Chinese NSF grant 19731001 and National 973 Information Technol- ogy High-Performance Software Program of China with grant No. G1998030401 The author gratefully acknowledges the support of K. C. Wong Education 

出 版 物：《Journal of Systems Science & Complexity》 (系统科学与复杂性学报（英文版）)

年 卷 期：2003年第16卷第2期

页      码：260-267页

摘      要：Using outward rotations, we obtain an approximation algorithm for MAXn/2-UNCUT problem, i.e., partitioning the vertices of a weighted graph into two blocks of equalcardinality such that the total weight of edges that do not cross the cut is maximized. In manyinteresting cases, the algorithm performs better than the algorithms of Ye and of Halperin andZwick. The main tool used to obtain this result is semidefinite programming.

主 题 词：approximation algorithm MAX n/2-UXCUT problem semidefinite programming approximation ratio 

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

核心收录：

馆 藏 号：203239154...