A randomized O( n)-competitive algorithm for the online connected facility location problem

DOI10.1007/S00453-016-0115-1zbMATH Open1355.68290OpenAlexW2280458302MaRDI QIDQ727979FDOQ727979

Authors: 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

Recommendations

• The online connected facility location problem
• The online multicommodity connected facility location problem
• scientific article; zbMATH DE number 2038744
• On the competitive ratio for online facility location
• The online prize-collecting facility location problem

zbMATH Keywords

online algorithmsrandomized algorithmsapproximation algorithmscompetitive analysisSteiner treeconnected facility location

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Discrete location and assignment (90B80)

Cites Work

• The design of approximation algorithms
• Title not available (Why is that?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
• Title not available (Why is that?)
• Dynamic Steiner Tree Problem
• Primal-dual algorithms for connected facility location problems
• Approximation Algorithms for Metric Facility Location Problems
• Connected facility location via random facility sampling and core detouring
• Offline and online facility leasing
• On the competitive ratio for online facility location
• Title not available (Why is that?)
• A primal-dual algorithm for online non-uniform facility location
• Cost-sharing mechanisms for network design
• Approximation via cost sharing
• Approximation algorithms for connected facility location problems
• Competitive algorithms for distributed data management.
• Online network design algorithms via hierarchical decompositions
• The online connected facility location problem

Cited In (6)

• Title not available (Why is that?)
• The online multicommodity connected facility location problem
• The online prize-collecting facility location problem
• The online connected facility location problem
• Online facility location with deletions
• Dynamic balanced graph partitioning

This page was built for publication: A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q727979)