A simple and deterministic competitive algorithm for online facility location

DOI10.1016/j.ic.2004.06.002zbMath1089.90036OpenAlexW2091503743WikidataQ116754425 ScholiaQ116754425MaRDI QIDQ703850

Aris Anagnostopoulos, Eli Upfal, Russell Bent, Pascal Van Hentenryck

Publication date: 11 January 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.06.002

zbMATH Keywords

Stochastic analysisCompetitive ratioOnline facility location

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Discrete location and assignment (90B80)

Related Items

The Post-Disaster Debris Clearance Problem Under Incomplete Information, Unnamed Item, Unnamed Item, A primal-dual algorithm for online non-uniform facility location, On the competitive ratio for online facility location, On the Facility Location Problem in Online and Dynamic Models., Online facility location with facility movements, Incremental algorithms for facility location and \(k\)-median, Online facility location with mobile facilities

Uses Software

• COMET

Cites Work

• A simple tabu search for warehouse location
• Uncapacitated facility location: General solution procedure and computational experience
• A data structure for arc insertion and regular path finding
• Solving the simple plant location problem by genetic algorithm
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Finding nearest neighbors in growth-restricted metrics
• A Dual-Based Procedure for Uncapacitated Facility Location
• Multidimensional binary search trees used for associative searching
• The Online Median Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item