Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center

Texto completo
Autor(es):
Fernandes, Cristina G. [1] ; de Paula, Samuel P. [1] ; Pedrosa, Lehilton L. C. [2]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Dept Comp Sci, Sao Paulo - Brazil
[2] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: ALGORITHMICA; v. 80, n. 3, SI, p. 1041-1072, MAR 2018.
Citações Web of Science: 2
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: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/14209-1 - Algoritmos de aproximação para problemas de projeto de rede com restrições
Beneficiário:Lehilton Lelis Chaves Pedrosa
Linha de fomento: Bolsas no Brasil - Pós-Doutorado