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

DOI10.1016/J.JDA.2006.03.001zbMath1134.90021OpenAlexW2004466770WikidataQ59818596 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

Continuous location (90B85) Inventory, storage, reservoirs (90B05)

Related Items (15)

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

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

This page was built for publication: A primal-dual algorithm for online non-uniform facility location