A simple and deterministic competitive algorithm for online facility location

DOI10.1016/J.IC.2004.06.002MaRDI QIDQ703850zbMATH OpenOpenAlexWikidataFDO

Authors Aris Anagnostopoulos, Russell Bent, Eli Upfal, 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

Competitive ratioStochastic analysisOnline facility location

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2038744
• On the competitive ratio for online facility location
• A primal-dual algorithm for online non-uniform facility location
• Online facility location with facility movements
• The Online Median Problem

Cites work

• scientific article; zbMATH DE number 1670526 (Why is no real title available?)
• scientific article; zbMATH DE number 4202014 (Why is no real title available?)
• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 1305496 (Why is no real title available?)
• scientific article; zbMATH DE number 1947060 (Why is no real title available?)
• scientific article; zbMATH DE number 2038744 (Why is no real title available?)
• scientific article; zbMATH DE number 1559542 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Dual-Based Procedure for Uncapacitated Facility Location
• A data structure for arc insertion and regular path finding
• A simple tabu search for warehouse location
• 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
• Multidimensional binary search trees used for associative searching
• Solving the simple plant location problem by genetic algorithm
• The Online Median Problem
• Uncapacitated facility location: General solution procedure and computational experience

Cited in

(12)

• On the competitive ratio for online facility location
• Online facility location with facility movements
• On the Facility Location Problem in Online and Dynamic Models.
• scientific article; zbMATH DE number 2038744 (Why is no real title available?)
• The online multicommodity connected facility location problem
• scientific article; zbMATH DE number 7378709 (Why is no real title available?)
• Incremental algorithms for facility location and \(k\)-median
• A primal-dual algorithm for online non-uniform facility location
• Online facility location against a \(t\)-bounded adversary
• Online facility location with mobile facilities
• Online facility location with deletions
• The post-disaster debris clearance problem under incomplete information

Describes a project that uses

Uses Software

• COMET

This page was built for publication: A simple and deterministic competitive algorithm for online facility location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703850)