| Texto completo | |
| Autor(es): |
San Felice, Mario Cesar
;
Williamson, David P.
;
Lee, Orlando
;
Pardo, A
;
Viola, A
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | LATIN 2014: THEORETICAL INFORMATICS; v. 8392, p. 12-pg., 2014-01-01. |
| Resumo | |
In this paper we propose the Online Connected Facility Location problem (OCFL), which is an online version of the Connected Facility Location problem (CFL). The CFL is a combination of the Un-capacitated Facility Location problem (FL) and the Steiner Tree problem (ST). We give a randomized O(log(2) n)-competitive algorithm for the OCFL via the sample-and-augment framework of Gupta, Kumar, Pal, and Roughgarden and previous algorithms for Online Facility Location (OFL) and Online Steiner Tree (OST). Also, we show that the same algorithm is a deterministic O(log n)-competitive algorithm for the special case of the OCFL with M = 1, where M is a scale factor for the edge costs. (AU) | |
| Processo FAPESP: | 12/06728-3 - Problemas online e incrementais de localização de instalações |
| Beneficiário: | Mário César San Felice |
| Modalidade de apoio: | Bolsas no Exterior - Estágio de Pesquisa - Doutorado |