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 ...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.展开更多
基金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. G1998030401The author gratefully acknowledges the support of K. C. Wong Education
文摘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.
