Paper Info
Title
The Online Connected Facility Location Problem.
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.
Year
DOI
Venue
2014
10.1007/978-3-642-54423-1_50
Lecture Notes in Computer Science
Keywords
Field
DocType
Online Algorithms,Competitive Analysis,Connected Facility Location,Steiner Tree,Approximation Algorithms,Randomized Algorithms
Scale factor,Discrete mathematics,Online algorithm,Randomized algorithm,Approximation algorithm,Steiner tree problem,Computer science,Facility location problem,Competitive analysis,Special case
Conference
Volume
ISSN
Citations 
8392
0302-9743
2
PageRank 
References 
Authors
0.39
13
3
Name
Order
Citations
PageRank
Mário César San Felice142.13
David P. Williamson23564413.34
Orlando Lee361.85