Offline and online facility leasing

DOI10.1016/j.disopt.2013.10.001zbMath1506.90141OpenAlexW2028294891MaRDI QIDQ1799393

David P. Williamson, Chandrashekhar Nagarajan

Publication date: 18 October 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2013.10.001

zbMATH Keywords

facility locationonline algorithmparking permit problemfacility leasing

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items

Multistage knapsack ⋮ The online prize-collecting facility location problem ⋮ On generalizations of the parking permit problem and network leasing problems ⋮ Group parking permit problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Leasing with Uncertainty ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Online multistage subset maximization problems ⋮ Unnamed Item ⋮ Online facility location with mobile facilities ⋮ LP-based algorithms for multistage minimization problems

Cites Work

• Unnamed Item
• A primal-dual algorithm for online non-uniform facility location
• On the competitive ratio for online facility location
• Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Offline and Online Facility Leasing
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A Greedy Heuristic for the Set-Covering Problem
• Infrastructure Leasing Problems

This page was built for publication: Offline and online facility leasing