Please use this identifier to cite or link to this item:
|Type:||Artigo de evento|
|Title:||The Online Connected Facility Location Problem|
|Author:||San Felice M.C.|
|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.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.