# Improved Bounds for Online Facility Location with Predictions

arXiv: https://arxiv.org/abs/2107.08277 · HTML: https://mlsanity.com/paper/2107.08277/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 17 Jul 2021.

## Builds on (most cited first, 10 of 10)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Better and Simpler Learning-Augmented Online Caching](https://mlsanity.com/paper/2005.13716/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [Online Facility Location with Deletions](https://mlsanity.com/paper/1807.03839/) (2018)

## Built on by (most cited first, 5 of 5)

- [Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets](https://mlsanity.com/paper/2211.06567/) (2022)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [Online TSP with Predictions](https://mlsanity.com/paper/2206.15364/) (2022)
- [Learning to Approximate Uniform Facility Location via Graph Neural Networks](https://mlsanity.com/paper/2602.13155/) (2026)
- [Learning-Augmented Algorithms for k-median via Online Learning](https://mlsanity.com/paper/2603.18157/) (2026)

## Abstract (arXiv)

We consider Online Facility Location in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We focus on uniform facility opening costs and present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases from sublogarithmic in the number of demands n to constant as the so-called η1 error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases. E.g., our analysis implies that if for some varepsilon > 0, η1 = OPT / n^varepsilon, where OPT is the cost of the optimal solution, the competitive ratio becomes O(1/varepsilon). We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the η1 error is optimal, up to constant factors. Finally, we evaluate our algorithm on real world data and compare the performance of our learning-augmented approach against the performance of the best known algorithm for OFL without predictions.