The online connected facility location problem

DOI10.1007/978-3-642-54423-1_50MaRDI QIDQ5405074zbMATH OpenOpenAlexFDO

Authors Mário César San Felice, David P. Williamson, Orlando Lee

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54423-1_50

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

• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• The online multicommodity connected facility location problem
• The online prize-collecting facility location problem
• Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
• Primal-dual algorithms for connected facility location problems

Cited in

(5)

• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• The online multicommodity connected facility location problem
• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• The online prize-collecting facility location problem
• Connected facility location via random facility sampling and core detouring

This page was built for publication: 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 Q5405074)