Artículos de revistas
A Randomized O(log N) -competitive Algorithm For The Online Connected Facility Location Problem
Registro en:
Algorithmica. Springer, v. 76, p. 1139 - 1157, 2016.
0178-4617
1432-0541
WOS:000387338900013
10.1007/s00453-016-0115-1
Autor
San Felice
Mario Cesar; Williamson
David P.; Lee
Orlando
Institución
Resumen
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. San Felice et al. (2014) presented a randomized algorithm for the OCFL and proved that it is -competitive, where n is the number of clients. That algorithm combines the sample-and-augment framework of Gupta, Kumar, Pal, and Roughgarden with previous algorithms for the Online Facility Location (OFL) and the Online Steiner Tree (OST) problems. In this paper we use a more precise analysis to show that the same algorithm is -competitive. Since there is a lower bound of for this problem, our result achieves the best possible competitive ratio, asymptotically. 76 4 1139 1157 Sao Paulo Research Foundation (FAPESP) [2009/15535-1] NSF [CCF-1115256] Bolsa de Produtividade do CNPq [303947/2008-0] Edital Universal CNPq [477692/2012-5] Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)