Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center
verfasst von : Cristina G. Fernandes, Samuel P. de Paula, Lehilton L. C. Pedrosa
Erschienen in: LATIN 2016: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated \(\alpha \)
-fault-tolerant k
-center, where centers have a limit on the number of assigned elements, and, if \(\alpha \) centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the \(\{0,L\}\)-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the previously best known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming \(\alpha \) is constant, our method leads to the first approximations for this case.