TY - JOUR
T1 - Fault tolerant K-center problems
AU - Khuller, Samir
AU - Pless, Robert
AU - Sussmann, Yoram J.
N1 - Funding Information:
E-mail address: samir@cs.umd.edu (S. Khuller). 1Research supported by NSF Research Initiation Award CCR-9307462, and NSF CAREER Award CCR-9501355. 2Research supported by NSF Grant IRI-90-57934. 3Research supported by NSF CAREER Award CCR-9501355.
PY - 2000/7/6
Y1 - 2000/7/6
N2 - 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 an approximation 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, assuming P ≠ NP. 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. For this version our approximation factor is 3. The best possible approximation factor for even the basic K-supplier problem is 3, assuming P ≠ NP.
AB - 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 an approximation 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, assuming P ≠ NP. 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. For this version our approximation factor is 3. The best possible approximation factor for even the basic K-supplier problem is 3, assuming P ≠ NP.
KW - Approximation algorithms
KW - Facility location
KW - Fault-tolerance
KW - K-center
UR - http://www.scopus.com/inward/record.url?scp=0041953557&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0041953557&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(98)00222-9
DO - 10.1016/S0304-3975(98)00222-9
M3 - Article
AN - SCOPUS:0041953557
VL - 242
SP - 237
EP - 245
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 1-2
ER -