论文部分内容阅读
Using outward rotations, we obtain an approximation algorithm for MAX n/2-UNCUT problem, i.e., partitioning the vertices of a weighted graph into two blocks of equal cardinality such that the total weight of edges that do not cross the cut is maximized. 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.