Busca avançada
Ano de início
Entree


The Online Connected Facility Location Problem

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