Approximation algorithms for maximum dispersion

被引：112

作者：

Hassin, R

Rubinstein, S

Tamir, A

机构：

[1] Dept. of Stat. and Operations Res., School of Mathematical Sciences, Tel-Aviv University, Ramat Aviv

来源：

OPERATIONS RESEARCH LETTERS | 1997年 / 21卷 / 03期

关键词：

approximation algorithms; maximum dispersion; facility location;

D O I：

10.1016/S0167-6377(97)00034-5

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We describe approximation algorithms with bounded performance guarantees for the following problem: A graph is given with edge weights satisfying the triangle inequality, together with two numbers k and p. Find k disjoint subsets of p vertices each, so that the total weight of edges within subsets is maximized. (C) 1997 Elsevier Science B.V.

引用

页码：133 / 137

页数：5

共 12 条

[1] [Anonymous], 1996, LNCS
[2] BLUM M, 1972, J COMPUT SYST SCI, V7, P448
[3] CHANDRA B, 1996, LECT NOTES COMPUTER, V1097, P53
[4] A CLASS OF BOUNDED APPROXIMATION ALGORITHMS FOR GRAPH PARTITIONING
FEO, TA
KHELLAF, M
[J]. NETWORKS, 1990, 20 (02) : 181 - 195
[5] GABOW HN, 1990, 1ST P ANN ACM SIAM S, P434
[6] GABOW HN, 1975, J ACM, V23, P221
[7] Computational aspects of the maximum diversity problem
Ghosh, JB
[J]. OPERATIONS RESEARCH LETTERS, 1996, 19 (04) : 175 - 181
[8] Korte B, 1978, ANN DISCRETE MATH, V2, P65, DOI [10.1016/S0167-5060(08)70322-4, DOI 10.1016/S0167-5060(08)70322-4]
[9] KORTSARZ G, 1993, AN S FDN CO, P692
[10] HEURISTIC AND SPECIAL CASE ALGORITHMS FOR DISPERSION PROBLEMS
RAVI, SS
ROSENKRANTZ, DJ
TAYI, GK
[J]. OPERATIONS RESEARCH, 1994, 42 (02) : 299 - 310

← 1 2 →