APPROXIMATION ALGORITHM FOR MAX-BISECTION PROBLEM WITH THE POSITIVE SEMIDEFINITE RELAXATION

• 来源期刊: 计算数学（英文版）
• 学科: 数学
• 关键词: Approximation algorithm Max-Bisection problem Semidefinite programming Approximation ratio.
• 年，卷（期）: 2003,（3）
• 页码范围: 357-366
• 页数: 10页
• 分类号: O1
• 语种: 英文

摘要

Using outward rotations, we obtain an approximation algorithm for Max-Bisectionproblem, i.e., partitioning the vertices of an undirected graph into two blocks of equalcardinality so as to maximize the weights of crossing edges. In many interesting cases, thealgorithm performs better than the algorithms of Ye and of Halperin and Zwick. The maintool used to obtain this result is semidefinite programming.