Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/88019
Type: Artigo de evento
Title: The Online Connected Facility Location Problem
Author: San Felice M.C.
Williamson D.P.
Lee O.
Abstract: 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 Uncapacitated Facility Location problem (FL) and the Steiner Tree problem (ST). We give a randomized O(log2 n)-competitive algorithm for the OCFL via the sample-and-augment framework of Gupta, Kumar, Pál, 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(logn)-competitive algorithm for the special case of the OCFL with M∈=∈1, where M is a scale factor for the edge costs. © 2014 Springer-Verlag Berlin Heidelberg.
Editor: Springer Verlag
Rights: fechado
Identifier DOI: 10.1007/978-3-642-54423-1_50
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-84899902285&partnerID=40&md5=a52170191da64c893ed87d98791f0c06
Date Issue: 2014
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-84899902285.pdf193.29 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.