๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The p-neighbor k-center problem

โœ Scribed by Shiva Chaudhuri; Naveen Garg; R. Ravi

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
389 KB
Volume
65
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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. @ 1998 Elsevier Science B.V.

๐Ÿ“œ SIMILAR VOLUMES

The k-neighbor domination problem
The k-neighbor domination problem
โœ Shiow-Fen Hwang; Gerard J. Chang ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 314 KB
On the rectangular p-center problem
On the rectangular p-center problem
โœ Zvi Drezner ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 322 KB

The p-center problem involves finding the best locations for p facilities such that the furthest among n points is as close as possible to one of the facilities. Rectangular (sometimes called rectilinear, Manhattan, or 1,) distances are considered. An O ( n ) algorithm for the 1-center problem, an O

On the k-center problem with many center
On the k-center problem with many centers
โœ WanSoo T. Rhee; Michel Talagrand ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 323 KB
Center-based nearest neighbor classifier
Center-based nearest neighbor classifier
โœ Qing-Bin Gao; Zheng-Zhi Wang ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 164 KB