A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
复制标题
DOI：
10.1002/rsa.10035
复制
发表时间：
2001-06
影响因子：
1
通讯作者：
E. Halperin;Uri Zwick
中科院分区：
文献类型：
--
作者：
E. Halperin;Uri Zwick
我们获得了所有自然最大二分线问题的基于半决赛的近似算法。从不同侧面连接顶点的边缘是最大的； $ nemens -subgraph-结合一半的顶点的集合，使得从该集合中连接两个顶点的总重量是最大化的；我们还考虑了这些问题的定向版本，例如超过2 $ directed -direction -bisection，以及2 $ directed uncut的最大$ n \这些结果可用于获得上面提到的分区问题的不平衡版本的改进近似算法$ n \超过2美元。最大2 -SAT和MAX DI -CUT FEIGE和GOEMANS的算法
We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX$n\over 2$‐BISECTION—partition the vertices of the graph into two sets of equal size such that the total weight of edges connecting vertices from different sides is maximized; MAX$n\over 2$‐VERTEX‐COVER—find a set containing half of the vertices such that the total weight of edges touching this set is maximized; MAX$n\over 2$‐DENSE‐SUBGRAPH—find a set containing half of the vertices such that the total weight of edges connecting two vertices from this set is maximized; and MAX$n\over 2$UNCUT—partition the vertices into two sets of equal size such that the total weight of edges that do not cross the cut is maximized. We also consider the directed versions of these problems, such as MAX$n\over 2$‐DIRECTED‐BISECTION and MAX$n\over 2$‐DIRECTED‐UNCUT. These results can be used to obtain improved approximation algorithms for the unbalanced versions of the partition problems mentioned above, where we want to partition the graph into two sets of size $k$ and $n - k$, where $k$ is not necessarily $n\over 2$. Our results improve, extend and unify results of Frieze and Jerrum, Feige and Langberg, Ye, and others. All these results may be viewed as extensions of the MAX CUT algorithm of Goemans and Williamson, and the MAX 2‐SAT and MAX DI‐CUT algorithms of Feige and Goemans. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:382–402, 2002