The online prize-collecting facility location problem

DOI10.1016/j.endm.2015.07.026zbMath1353.90080OpenAlexW2198946070MaRDI QIDQ324761

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

Publication date: 17 October 2016

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

zbMATH Keywords

primal-dual methodcompetitive analysisonline algorithmsprize-collecting facility location problem

Mathematics Subject Classification ID

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

Cites Work

• A primal-dual algorithm for online non-uniform facility location
• An improved approximation algorithm for uncapacitated facility location problem with penalties
• Offline and online facility leasing
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• On the competitive ratio for online facility location
• Approximation Algorithms for Metric Facility Location Problems
• An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem
• Unnamed Item
• Unnamed Item

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