A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
From MaRDI portal
Publication:727979
DOI10.1007/S00453-016-0115-1zbMath1355.68290OpenAlexW2280458302MaRDI QIDQ727979
David P. Williamson, Orlando Lee, Mário César San Felice
Publication date: 21 December 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-016-0115-1
competitive analysisonline algorithmsapproximation algorithmsrandomized algorithmsSteiner treeconnected facility location
Discrete location and assignment (90B80) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A primal-dual algorithm for online non-uniform facility location
- Competitive algorithms for distributed data management.
- Approximation algorithms for connected facility location problems
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- Offline and online facility leasing
- Primal-dual algorithms for connected facility location problems
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Connected facility location via random facility sampling and core detouring
- On the competitive ratio for online facility location
- Cost-sharing mechanisms for network design
- The Design of Approximation Algorithms
- Approximation Algorithms for Metric Facility Location Problems
- Approximation via cost sharing
- The Design of Competitive Online Algorithms via a Primal—Dual Approach
- Dynamic Steiner Tree Problem
- Online Network Design Algorithms via Hierarchical Decompositions
- The Online Connected Facility Location Problem
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
This page was built for publication: A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
