The online prize-collecting facility location problem

DOI10.1016/J.ENDM.2015.07.026MaRDI QIDQ324761zbMATH OpenOpenAlexFDO

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

Publication date 17 October 2016

Full work available at URL https://doi.org/10.1016/j.endm.2015.07.026

zbMATH Keywords

online algorithmscompetitive analysisprimal-dual methodprize-collecting facility location problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Recommendations

• The online connected facility location problem
• A primal-dual algorithm for online non-uniform facility location
• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• The online prize-collecting traveling salesman problem
• The online multicommodity connected 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?)
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A primal-dual algorithm for online non-uniform facility location
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem
• Approximation Algorithms for Metric Facility Location Problems
• Offline and online facility leasing
• On the competitive ratio for online facility location

Cited in

(3)

• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• The online prize-collecting traveling salesman problem
• The online connected facility location problem

This page was built for publication: The online prize-collecting facility location problem

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