# Fault Tolerant K-Center Problems

 dc.contributor.author Khuller, Samir en_US dc.contributor.author Pless, Robert en_US dc.contributor.author Sussmann, Yoram J. en_US dc.date.accessioned 2004-05-31T22:39:36Z dc.date.available 2004-05-31T22:39:36Z dc.date.created 1996-06 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/823 dc.description.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 $\alpha$ ($\alpha \le 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 $\alpha$ centers close to it. In the second version, each vertex that {\em does not have a center placed on it} is required to have at least $\alpha$ centers close to it. For both these versions we are able to provide polynomial time approximation algorithms that achieve constant approximation factors for {\em any} $\alpha$. For the first version we give an algorithm that achieves an approximation factor of $3$ for any $\alpha$, and achieves an approximation factor of $2$ for $\alpha < 4$. For the second version, we provide algorithms with approximation factors of $2$ for any $\alpha$. 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 $\alpha$ 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. (Also cross-referenced as UMIACS-TR-96-40) en_US dc.format.extent 186556 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3652 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-96-40 en_US dc.title Fault Tolerant K-Center Problems en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿