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

DOI10.1007/S00453-016-0115-1MaRDI QIDQ727979zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(6)

• Dynamic balanced graph partitioning
• scientific article; zbMATH DE number 2038744 (Why is no real title available?)
• The online connected facility location problem
• The online prize-collecting facility location problem
• Online facility location with deletions
• The online multicommodity connected facility location problem

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)