A SIMPLE HEURISTIC FOR THE P-CENTER PROBLEM

被引：115
作者：
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 [J].
DREZNER, Z .
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 [J].
FOWLER, RJ ;
PATERSON, MS ;
TANIMOTO, SL .
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 [J].
HSU, WL ;
NEMHAUSER, GL .
DISCRETE APPLIED MATHEMATICS, 1979, 1 (03) :209-215
[7]   ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .1. P-CENTERS [J].
KARIV, O ;
HAKIMI, SL .
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 [J].
MEGIDDO, N ;
SUPOWIT, KJ .
SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :182-196
1