MIN-CUT CLUSTERING

被引：149

作者：

JOHNSON, EL ^{[1
]}

MEHROTRA, A ^{[1
]}

NEMHAUSER, GL ^{[1
]}

机构：

[1] GEORGIA INST TECHNOL,SCH IND & SYST ENGN,ATLANTA,GA 30332

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 62卷 / 01期

关键词：

CLUSTERING; DECOMPOSITION; COLUMN GENERATION; SUBPROBLEM OPTIMIZATION; VALID INEQUALITY; COMPILER DESIGN;

D O I：

10.1007/BF01585164

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We describe a decomposition framework and a column generation scheme for solving a min-cut clustering problem. The subproblem to generate additional columns is itself an NP-hard mixed integer programming problem. We discuss strong valid inequalities for the subproblem and describe some efficient solution strategies. Computational results on compiler construction problems are reported.

引用

页码：133 / 151

页数：19

共 16 条

[1] ON THE CUT POLYTOPE [J].

BARAHONA, F ;

MAHJOUB, AR .

MATHEMATICAL PROGRAMMING, 1986, 36 (02) :157-173

[2]

CHOPRA S, 1991, FACETS K PARTITION P

[3]

CHOPRA S, 1990, PARTITION PROBLEM

[4]

CHOPRA S, 1991, GRAPH PARTITIONING P

[5] THE EQUIPARTITION POLYTOPE .2. VALID INEQUALITIES AND FACETS [J].

CONFORTI, M ;

RAO, MR ;

SASSANO, A .

MATHEMATICAL PROGRAMMING, 1990, 49 (01) :71-90

[6] THE EQUIPARTITION POLYTOPE .1. FORMULATIONS, DIMENSION AND BASIC FACETS [J].

CONFORTI, M ;

RAO, MR ;

SASSANO, A .

MATHEMATICAL PROGRAMMING, 1990, 49 (01) :49-70

[7]

DAHLAUS E, 1983, COMPLEXITY MULTIWAY

[8]

Garey M. R., 1979, COMPUTERS INTRACTABI

[9]

GOLDSCHMIDT O, 1985, 29TH P ANN S F COMP, P444

[10] A CUTTING PLANE ALGORITHM FOR A CLUSTERING PROBLEM [J].

GROTSCHEL, M ;

WAKABAYASHI, Y .

MATHEMATICAL PROGRAMMING, 1989, 45 (01) :59-96

← 1 2 →