A .699-approximation algorithm for Max-Bisection

被引：105

作者：

Ye, YY ^{[1
]}

机构：

[1] Univ Iowa, Dept Management Sci, Henry B Tippie Coll Business, Iowa City, IA 52242 USA

来源：

MATHEMATICAL PROGRAMMING | 2001年 / 90卷 / 01期

关键词：

graph bisection; polynomial-time approximation algorithm; semidefinite programming;

D O I：

10.1007/PL00011415

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 [计算机软件与理论]; 0835 [软件工程];

摘要：

We present a .699-approximation algorithm fur Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson.

引用

页码：101 / 111

页数：11

共 5 条

[1]

BERTSIMAS D, 1998, HDB COMBINATORIAL OP, V3, P1

[2]

Early childhood risk and protective factors for substance use during early adolescence: Gender differences [J].

Friedman, AS ;

Bransfield, S ;

Granick, S ;

Kreisher, C .

JOURNAL OF CHILD & ADOLESCENT SUBSTANCE ABUSE, 1995, 4 (04) :1-23

[3]

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[4]

Semidefinite relaxation and nonconvex quadratic optimization [J].

Nesterov, Y .

OPTIMIZATION METHODS & SOFTWARE, 1998, 9 (1-3) :141-160

[5]

ZWICK U, 1999, P 10 ACM S DISCR ALG

← 1 →