The p-neighbor k-center problem

被引：38

作者：

Chaudhuri, S ^{[1
]}

Garg, N ^{[1
]}

Ravi, R ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Grad Sch Ind Adm, Pittsburgh, PA 15213 USA

来源：

INFORMATION PROCESSING LETTERS | 1998年 / 65卷 / 03期

关键词：

design of algorithms; facility location; centers; approximation algorithms;

D O I：

10.1016/S0020-0190(97)00224-X

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The k-center problem with triangle inequality is that of placing k center nodes in a weighted undirected graph in which the edge weights obey the triangle inequality, so that the maximum distance of any node to its nearest center is minimized. In this paper, we consider a generalization of this problem where, given a number p, we wish to place k centers so as to minimize the maximum distance of any non-center node to its pth closest center. We derive a best possible approximation algorithm for this problem. (C) 1998 Elsevier Science B.V.

引用

页码：131 / 134

页数：4

共 12 条

[1]

Feder T., 1988, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, P434, DOI 10.1145/62212.62255

[2] CLUSTERING TO MINIMIZE THE MAXIMUM INTERCLUSTER DISTANCE [J].

GONZALEZ, TF .

THEORETICAL COMPUTER SCIENCE, 1985, 38 (2-3) :293-306

[3]

Handler G.Y., 1979, MIT Press Series in Signal Processing, Optimization, and Control

[4] A UNIFIED APPROACH TO APPROXIMATION ALGORITHMS FOR BOTTLENECK PROBLEMS [J].

HOCHBAUM, DS ;

SHMOYS, DB .

JOURNAL OF THE ACM, 1986, 33 (03) :533-550

[5] A BEST POSSIBLE HEURISTIC FOR THE K-CENTER PROBLEM [J].

HOCHBAUM, DS ;

SHMOYS, DB .

MATHEMATICS OF OPERATIONS RESEARCH, 1985, 10 (02) :180-184

[6] ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .1. P-CENTERS [J].

KARIV, O ;

HAKIMI, SL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1979, 37 (03) :513-538

[7]

KHULLER S, UMIACSTR9640

[8]

KHULLER S, 1997, IN PRESS P 3 INT C A

[9] ON A GENERALIZATION OF THE P-CENTER PROBLEM [J].

KRUMKE, SO .

INFORMATION PROCESSING LETTERS, 1995, 56 (02) :67-71

[10] A HEURISTIC FOR THE P-CENTER PROBLEM IN GRAPHS [J].

PLESNIK, J .

DISCRETE APPLIED MATHEMATICS, 1987, 17 (03) :263-268

← 1 2 →