| Texto completo | |
| Autor(es): |
Fernandes, Cristina G.
;
de Paula, Samuel P.
;
Pedrosa, Lehilton L. C.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ALGORITHMICA; v. 80, n. 3, p. 32-pg., 2018-03-01. |
| Resumo | |
In the -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 -fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if any 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 -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 best previously known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault-tolerant k-supplier problem. (AU) | |
| Processo FAPESP: | 14/14209-1 - Algoritmos de aproximação para problemas de projeto de rede com restrições |
| Beneficiário: | Lehilton Lelis Chaves Pedrosa |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |