摘要
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. G1998030401
The author gratefully acknowledges the support of K. C. Wong Education
