The online connected facility location problem

DOI10.1007/978-3-642-54423-1_50zbMATH Open1352.68286OpenAlexW2125315581MaRDI QIDQ5405074FDOQ5405074

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

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

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)

Cited In (5)

• Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem
• 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
• 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)