1/2 APPROXIMATION ALGORITHMS FOR THE KAPPA-PARTITION PROBLEM

被引：23

作者：

FEO, T ^{[1
]}

GOLDSCHMIDT, O ^{[1
]}

KHELLAF, M ^{[1
]}

机构：

[1] BRITISH TELECOM TYMNET, PARIS, FRANCE

来源：

OPERATIONS RESEARCH | 1992年 / 40卷

关键词：

D O I：

10.1287/opre.40.1.S170

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The k-partition problem seeks to cluster the vertices of an edge-weighted graph, G = (V,E), into k sets of \V\/k vertices each, such that the total weight of the edges having both endpoints in the same cluster is maximized. Bottom-up type heuristics based on matchings are presented for this problem. These heuristics are shown to yield solutions that are at least one-half the weight of the optimal solution for k equal to \V\/3 and \V\/4.

引用

页码：S170 / S173

页数：4

共 7 条

[1]

Chen C. C., 1986, THESIS U CALIFORNIA

[2] A CLASS OF BOUNDED APPROXIMATION ALGORITHMS FOR GRAPH PARTITIONING [J].

FEO, TA ;

KHELLAF, M .

NETWORKS, 1990, 20 (02) :181-195

[3]

FEO TA, 1988, HALF APPROXIMATION A

[4]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[5]

Kernighan B. W., 1970, Bell System Technical Journal, V49, P291

[6]

Kral J., 1965, INFORM PROCESSING MA, V2, P116

[7]

Papadimitriou C. H., 1998, COMBINATORIAL OPTIMI

← 1 →