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 ratioOnline facility locationStochastic analysis

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

• A data structure for arc insertion and regular path finding
• A Dual-Based Procedure for Uncapacitated Facility Location
• 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
• 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?)
• 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

(15)

• The online multicommodity connected facility location problem
• 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
• scientific article; zbMATH DE number 2038744 (Why is no real title available?)
• Online facility location against a \(t\)-bounded adversary
• Online facility location with deletions
• scientific article; zbMATH DE number 7378709 (Why is no real title available?)
• Online facility location with facility movements
• On the Facility Location Problem in Online and Dynamic Models.
• Online facility location with weights and congestion
• On competitive ratio for online uniform facility location problem in random-order model
• A nearly optimal deterministic online algorithm for non-metric facility location
• A primal-dual algorithm for online non-uniform facility location

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)