Fault tolerant K-center problems

Samir Khuller, Robert Pless, Yoram J. Sussmann

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

4 Scopus citations

Abstract

The basic 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. This problem is known to be NP-hard, and several optimal approximation algorithms that achieve a factor of 2 have been developed for it. We focus our attention on a generalization of this problem, where each vertex is required to have a set of α (α≤K) centers close to it. In particular, we study two different versions of this problem. In the first version, each vertex is required to have at least α centers close to it. In the second version, each vertex that does not have a center placed on it is required to have at least α centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for any α. For the first version we give an algorithm that achieves an approximation factor of 3 for any α, and achieves an approximation factor of 2 for α<4. For the second version, we provide algorithms with approximation factors of 2 for any α. The best possible approximation factor for even the basic K-center problem is 2. In addition, we give a polynomial time approximation algorithm for a generalization of the K-supplier problem where a subset of at most K supplier nodes must be selected as centers so that every demand node has at least α centers close to it. We also provide polynomial time approximation algorithms for all the above problems for generalizations when cost and weight functions are defined on the set of vertices.

Original languageEnglish (US)
Title of host publicationAlgorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings
EditorsGiancarlo Bongiovanni, Daniel Pierre Bovet, Giuseppe Di Battista
PublisherSpringer Verlag
Pages37-48
Number of pages12
ISBN (Print)3540625925, 9783540625926
DOIs
StatePublished - 1997
Event3rd Italian Conference on Algorithms and Complexity, CIAC 1997 - Rome, Italy
Duration: Mar 12 1997Mar 14 1997

Publication series

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

Other

Other3rd Italian Conference on Algorithms and Complexity, CIAC 1997
CountryItaly
CityRome
Period3/12/973/14/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fault tolerant K-center problems'. Together they form a unique fingerprint.

Cite this