On the Facility Location Problem in Online and Dynamic Models.

DOI10.4230/lipics.approx/random.2020.42OpenAlexW3082244983MaRDI QIDQ6084398

Janardhan Kulkarni, Jiayi Xian, Xiangyu Guo, Shi Li

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

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

Cites Work

• A simple and deterministic competitive algorithm for online facility location
• A primal-dual algorithm for online non-uniform facility location
• A 1.488 approximation algorithm for the uncapacitated facility location problem
• On the competitive ratio for online facility location
• Incremental algorithms for facility location and \(k\)-median
• The Design of Approximation Algorithms
• Memoryless facility location in one pass
• Local search heuristic for k-median and facility location problems
• k-server via multiscale entropic regularization
• Improved Combinatorial Algorithms for Facility Location Problems
• Online Network Design Algorithms via Hierarchical Decompositions
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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