A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
type: Item
instance of: scholarly article
title: A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
zbMATH Open document ID: 1355.68290
author: David P. Williamson
author: Orlando Lee
author: Mário César San Felice
published in: Algorithmica
publication date: 2016-12-21T00:00:00Z
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 6667669
zbMATH Keywords: online algorithms
zbMATH Keywords: competitive analysis
zbMATH Keywords: connected facility location
zbMATH Keywords: Steiner tree
zbMATH Keywords: approximation algorithms
zbMATH Keywords: randomized algorithms
MaRDI profile type: Publication
full work available at URL: s00453-016-0115-1
OpenAlex ID: W2280458302
cites work: Competitive algorithms for distributed data management.
cites work: Q4223058
cites work: The Design of Competitive Online Algorithms via a Primal—Dual Approach
cites work: An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
cites work: Connected facility location via random facility sampling and core detouring
cites work: A primal-dual algorithm for online non-uniform facility location
cites work: On the competitive ratio for online facility location
cites work: Approximation via cost sharing
cites work: Cost-sharing mechanisms for network design
cites work: Approximation algorithms for connected facility location problems
cites work: Dynamic Steiner Tree Problem
cites work: A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
cites work: A 1.488 approximation algorithm for the uncapacitated facility location problem
cites work: Approximation Algorithms for Metric Facility Location Problems
cites work: Offline and online facility leasing
cites work: The Online Connected Facility Location Problem
cites work: Q2753723
cites work: Primal-dual algorithms for connected facility location problems
cites work: Online Network Design Algorithms via Hierarchical Decompositions
cites work: Q4258215
cites work: The Design of Approximation Algorithms
DOI: 10.1007/S00453-016-0115-1
description: scientific article; zbMATH DE number 6667669