# Online Facility Location with Predictions

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2021.

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

- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets](https://mlsanity.com/paper/2211.06567/) (2022)
- [Online Classification with Predictions](https://mlsanity.com/paper/2405.14066/) (2024)
- [Learning-Augmented Search Data Structures](https://mlsanity.com/paper/2402.10457/) (2024)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)
- [A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives](https://mlsanity.com/paper/2406.03574/) (2024)
- [Efficient Approximate Temporal Triangle Counting in Streaming with Predictions](https://mlsanity.com/paper/2506.13173/) (2025)
- [Prediction-Augmented Mechanism Design for Weighted Facility Location](https://mlsanity.com/paper/2507.06509/) (2025)
- [Mechanism Design for Facility Location using Predictions](https://mlsanity.com/paper/2508.03818/) (2025)
- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)
- [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 provide nearly optimal algorithms for online facility location (OFL) with predictions. In OFL, n demand points arrive in order and the algorithm must irrevocably assign each demand point to an open facility upon its arrival. The objective is to minimize the total connection costs from demand points to assigned facilities plus the facility opening cost. We further assume the algorithm is additionally given for each demand point xi a natural prediction fxipred which is supposed to be the facility fxiopt that serves xi in the offline optimal solution. Our main result is an O(minlog fracnη_∞OPT, logn )-competitive algorithm where η_∞ is the maximum prediction error (i.e., the distance between fxipred and fxiopt). Our algorithm overcomes the fundamental Omega(fraclog nlog log n) lower bound of OFL (without predictions) when η_∞ is small, and it still maintains O(log n) ratio even when η_∞ is unbounded. Furthermore, our theoretical analysis is supported by empirical evaluations for the tradeoffs between η_∞ and the competitive ratio on various real datasets of different types.