Improved approximation algorithms for MAX k-CUT and MAX BISECTION

被引：254

作者：

Frieze, A ^{[1
]}

Jerrum, M ^{[1
]}

机构：

[1] UNIV EDINBURGH,DEPT COMP SCI,EDINBURGH EH9 3JZ,MIDLOTHIAN,SCOTLAND

来源：

ALGORITHMICA | 1997年 / 18卷 / 01期

关键词：

approximation algorithms; combinatorial optimization; graph connectivity; randomized algorithms; semidefinite programming;

D O I：

10.1007/BF02523688

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：67 / 81

页数：15

共 17 条

[1] INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].

ALIZADEH, F .

SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51

[2]

Arora S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P284, DOI 10.1145/225058.225140

[3]

ARORA S, 1992, 33RD P IEEE S F COMP, P14

[4] THE CORRELATION OF MAXIMA IN SAMPLES DRAWN FROM A BIVARIATE NORMAL-DISTRIBUTION [J].

BOFINGER, E ;

BOFINGER, VJ .

AUSTRALIAN JOURNAL OF STATISTICS, 1965, 7 (03) :57-61

[5]

DAVID HA, 1980, ORDER STATISTICS

[6]

delaVega WF, 1996, RANDOM STRUCT ALGOR, V8, P187, DOI 10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO

[7]

2-U

[8]

Galambos J., 1978, The asymptotic theory of extreme order statistics

[9]

Goemans M. X., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P422, DOI 10.1145/195058.195216

[10]

KANN V, 1995, TRITANA9505 ROY I TE

← 1 2 →