Improved approximation algorithms for MAX k-CUT and MAX BISECTION
Improved approximation algorithms for MAX k-CUT and MAX BISECTION
复制标题
DOI：
10.1007/bf02523688
复制
发表时间：
1997-05-01
期刊：
影响因子：
1.1
通讯作者：
Jerrum, M
中科院分区：
文献类型：
--
作者：
Frieze, A;Jerrum, M
对于（a）将加权图的顶点划分为k个块以使交叉边的权最大化和（B）将加权图的顶点划分为两个基数相等的块以使交叉边的权最大化的问题，给出了具有非平凡性能保证的多项式时间近似算法.该方法是由Goemans和威廉姆森首先提出的，是通过半定规划松弛。
Polynomial-time approximation algorithms with nontrivial performance guarantees are presented for the problems of (a) partitioning the vertices of a weighted graph into k blocks so as to maximize the weight of crossing edges, and (b) partitioning the vertices of a weighted graph into two blocks of equal cardinality, again so as to maximize the weight of crossing edges. The approach, pioneered by Goemans and Williamson, is via a semidefinite programming relaxation.