The Capacitated K-Center Problem
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 13 (3) , 403-418
- https://doi.org/10.1137/s0895480197329776
Abstract
The capacitated K-center problem is a basic facility location problem, where we are asked to locate K facilities in a graph and to assign vertices to facilities, so as to minimize the maximum distance from a vertex to the facility to which it is assigned. Moreover, each facility may be assigned at most L vertices. This problem is known to be NP-hard. We give polynomial time approximation algorithms for two different versions of this problem that achieve approximation factors of 5 and 6. We also study some generalizations of this problem.Keywords
This publication has 12 references indexed in Scilit:
- Data Collection for the Sloan Digital Sky Survey—A Network-Flow HeuristicJournal of Algorithms, 1998
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- How to Allocate Network CentersJournal of Algorithms, 1993
- A unified approach to approximation algorithms for bottleneck problemsJournal of the ACM, 1986
- A Best Possible Heuristic for the k-Center ProblemMathematics of Operations Research, 1985
- A simple heuristic for the p-centre problemOperations Research Letters, 1985
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985
- Easy and hard bottleneck location problemsDiscrete Applied Mathematics, 1979
- Optimal program and data locations in computer networksCommunications of the ACM, 1977
- Bottleneck extremaJournal of Combinatorial Theory, 1970