A SIMPLE HEURISTIC FOR THE P-CENTER PROBLEM

被引：113

作者：

DYER, ME

FRIEZE, AM

机构：

[1] CARNEGIE MELLON UNIV,GRAD SCH IND ADM,PITTSBURGH,PA 15213

[2] UNIV LONDON QUEEN MARY COLL,DEPT COMP SCI & STAT,LONDON E1 4NS,ENGLAND

来源：

OPERATIONS RESEARCH LETTERS | 1985年 / 3卷 / 06期

关键词：

D O I：

10.1016/0167-6377(85)90002-1

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

A description is given of a simple heuristic for determining the p-center of a finite set of weighted points in an arbitrary metric space. The computational effort is O(np) for an n-point set. The authors show that the ratio of the objective function value of the heuristic solution to that of the optimum is bounded by min(3, 1 plus alpha ), where alpha is the maximum weight divided by the minimum weight of points in the set.

引用

页码：285 / 288

页数：4

共 9 条

[1] THE P-CENTER PROBLEM - HEURISTIC AND OPTIMAL-ALGORITHMS
DREZNER, Z
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1984, 35 (08) : 741 - 748
[2] DYER ME, 1984, MULTIDIMENSIONAL SEA
[3] OPTIMAL PACKING AND COVERING IN THE PLANE ARE NP-COMPLETE
FOWLER, RJ
PATERSON, MS
TANIMOTO, SL
[J]. INFORMATION PROCESSING LETTERS, 1981, 12 (03) : 133 - 137
[4] HOCHBAUM DS, 1984, 16TH P ANN ACM S THE
[5] HOCHBAUM DS, 1983, BEST POSSIBLE HEURIS
[6] EASY AND HARD BOTTLENECK LOCATION-PROBLEMS
HSU, WL
NEMHAUSER, GL
[J]. DISCRETE APPLIED MATHEMATICS, 1979, 1 (03) : 209 - 215
[7] ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .1. P-CENTERS
KARIV, O
HAKIMI, SL
[J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1979, 37 (03) : 513 - 538
[8] Masuyama S., 1981, Transactions of the Institute of Electronics and Communication Engineers of Japan, Section E (English), VE64, P57
[9] ON THE COMPLEXITY OF SOME COMMON GEOMETRIC LOCATION-PROBLEMS
MEGIDDO, N
SUPOWIT, KJ
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (01) : 182 - 196

← 1 →