## Fault Tolerant K-Center Problems

##### View/Open

##### Date

1998-10-15##### Author

Khuller, Samir

Pless, Robert

Sussmann, Yoram J.

##### Metadata

Show full item record##### 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)

University of Maryland, College Park, MD 20742-7011 (301)314-1328.

Please send us your comments.