1/2 APPROXIMATION ALGORITHMS FOR THE KAPPA-PARTITION PROBLEM
成果类型：
Note
署名作者：
FEO, T; GOLDSCHMIDT, O; KHELLAF, M
署名单位：
British Telecom (BT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.S170
发表日期：
1992
页码：
S170-S173
关键词：
摘要：
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.