A simple and deterministic competitive algorithm for online facility location

DOI10.1016/j.ic.2004.06.002zbMath1089.90036WikidataQ116754425 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

68W40: Analysis of algorithms

90B80: Discrete location and assignment

Related Items

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

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