A primal-dual algorithm for online non-uniform facility location

DOI10.1016/j.jda.2006.03.001zbMath1134.90021WikidataQ59818596 ScholiaQ59818596MaRDI QIDQ924552

Dimitris Fotakis

Publication date: 16 May 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.03.001

zbMATH Keywords

competitive analysisonline algorithmsmetric facility location

Mathematics Subject Classification ID

90B85: Continuous location

90B05: Inventory, storage, reservoirs

Related Items

Unnamed Item, Unnamed Item, On the Facility Location Problem in Online and Dynamic Models., The online prize-collecting facility location problem, Towards the price of leasing online, An online 2-dimensional clustering problem with variable sized clusters, Online facility location with facility movements, A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem, Towards flexible demands in online leasing problems, Offline and online facility leasing, Online clustering with variable sized clusters, Online facility location with mobile facilities, Group parking permit problems, Randomized Online Algorithms for Set Cover Leasing Problems, Offline and Online Facility Leasing

Cites Work

• A simple and deterministic competitive algorithm for online facility location
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A new greedy approach for facility location problems
• Local search heuristic for k-median and facility location problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item