The capacitated K-center problem

Samir Khuller*, Yoram J. Sussmann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

90 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)403-418
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Volume13
Issue number3
DOIs
StatePublished - 2000

Keywords

  • Approximation algorithms
  • Facility location
  • K-center

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'The capacitated K-center problem'. Together they form a unique fingerprint.

Cite this