On the Facility Location Problem in Online and Dynamic Models.

DOI10.4230/LIPICS.APPROX/RANDOM.2020.42MaRDI QIDQ6084398zbMATH OpenOpenAlexFDO

Authors Xiangyu Guo, Janardhan Kulkarni, Shi Li, Jiayi Xian

Publication date 31 October 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12645/pdf/LIPIcs-APPROX42.pdf/

zbMATH Keywords

facility locationonline algorithmrecourse

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• \(k\)-server via multiscale entropic regularization
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• A primal-dual algorithm for online non-uniform facility location
• A simple and deterministic competitive algorithm for online facility location
• A tight bound on approximating arbitrary metrics by tree metrics
• Dynamic clustering to minimize the sum of radii
• scientific article; zbMATH DE number 1303608 (Why is no real title available?)
• scientific article; zbMATH DE number 7378709 (Why is no real title available?)
• scientific article; zbMATH DE number 7204478 (Why is no real title available?)
• Improved Combinatorial Algorithms for Facility Location Problems
• Incremental algorithms for facility location and \(k\)-median
• Local search heuristic for k-median and facility location problems
• Memoryless facility location in one pass
• On the competitive ratio for online facility location
• Online facility location with deletions
• Online network design algorithms via hierarchical decompositions
• The design of approximation algorithms

Cited in

(2)

• The online multicommodity connected facility location problem
• Adaptive-adversary-robust algorithms via small copy tree embeddings

This page was built for publication: On the Facility Location Problem in Online and Dynamic Models.

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