The capacitated K-center problem (Extended abstract)

Samir Khuller, Yoram J. Sussmann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

The capacitated K-center problem is a fundamental 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 s 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)
Title of host publicationAlgorithms - ESA 1996 - 4th Annual European Symposium, Proceedings
EditorsJosep Diaz, Maria Serna
PublisherSpringer Verlag
Pages152-166
Number of pages15
ISBN (Print)3540616802, 9783540616801
DOIs
StatePublished - 1996
Event4th European Symposium on Algorithms, ESA 1996 - Barcelona, Spain
Duration: Sep 25 1996Sep 27 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1136
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th European Symposium on Algorithms, ESA 1996
CountrySpain
CityBarcelona
Period9/25/969/27/96

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this