| Full text | |
| Author(s): |
San Felice, Mario Cesar
;
Williamson, David P.
;
Lee, Orlando
;
Pardo, A
;
Viola, A
Total Authors: 5
|
| Document type: | Journal article |
| Source: | LATIN 2014: THEORETICAL INFORMATICS; v. 8392, p. 12-pg., 2014-01-01. |
| 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 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) | |
| FAPESP's process: | 12/06728-3 - Online and incremental facility location problems |
| Grantee: | Mário César San Felice |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate |