Research map / Bandits and online learning / Online convex optimization and games
Improved Bounds for Online Facility Location with Predictions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a learning-augmented randomized algorithm for uniform-cost online facility location that uses predicted optimal facility locations, with a competitive ratio that improves from logarithmic to constant as the total prediction error η1 decreases, plus a matching lower bound and experiments on real and synthetic data.
Problem
Online facility location (OFL) where demands arrive one at a time and must be irrevocably assigned; each demand comes with a prediction of its optimal facility location, and the goal is a competitive ratio that depends on the total prediction error η1 and maximum error η∞.
Approach
A Meyerson-style randomized algorithm that opens facilities at predicted locations (with probability proportional to the distance from the prediction to the nearest open facility), analyzed via phases and balls to get a competitive ratio depending on η1, combined with a cost-doubling combiner with Meyerson-style demand-based algorithm to get min of both bounds.
Key results
- The algorithm is 2-consistent and its competitive ratio improves from sublogarithmic to O(1/eps) when η1 = opt/n^eps, matched by a lower bound Ω(log(αn)/log(log(αn)/β)) up to constants.
- The combined algorithm achieves competitive ratio min{9 n η∞/opt + 6, O(log min{nη∞/opt, n} / log(max{opt/η1,1} log min{...}))}.
- Experimentally, the predicted-location algorithm's competitive ratio converges smoothly to Meyerson's as prediction error α increases from 0 to 1 on all three datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase prediction error using alpha_predictor | PredOFL · CoverType, US Census, and synthetic grid | competitive ratio | Hurt |
| increase prediction-error standard deviation with gaussian_predictor | PredOFL · CoverType, US Census, and synthetic grid | competitive ratio | Helped |
| use random_perturb_predictor instead of unreflected predictions | PredOFL · CoverType, US Census, and synthetic grid | competitive ratio | Hurt |
| increase alpha with random_perturb_predictor toward 0.5 | PredOFL · CoverType, US Census, and synthetic grid | competitive ratio | Hurt |
Surprising findings
- For Gaussian predictions, the competitive ratio slightly improves as the standard deviation of prediction error increases.
- With random-reflection predictions, the algorithm only matches Meyerson's ratio once α approaches 0.5.
Limitations
- Analysis of the combined algorithm is restricted to uniform facility costs.
- Experiments are limited to a few datasets and a single pair of Meyerson-style algorithms; the combined algorithm is not separately evaluated in experiments as far as the text states.
- The lower bound holds for randomized algorithms but the matching is only up to constant factors and requires specific parameter ranges (e.g., β > 3α).
Experimental setup
Datasets: CoverType US Census synthetic uniform grid dataset
Benchmarks: CoverType US Census synthetic 2K-point grid dataset
Metrics: competitive ratio
Baselines: Meyerson's algorithm (MeyOFL) Jiang et al. prediction-based OFL algorithm
Builds on: Meyerson's online facility location algorithm Jiang et al. learning-augmented OFL cost doubling Lykouris and Vassilvitskii learning-augmented framework
Closest papers by meaning
- Online Facility Location with Predictions (ICLR 2022 · similarity 0.96)
- Learning-Augmented Online Covering Problems (ICML 2026 · similarity 0.88)
- Discrete-Smoothness in Online Algorithms with Predictions (NeurIPS 2023 · similarity 0.87)
- Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms (NeurIPS 2020 · similarity 0.87)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.86)
- MAC Advice for facility location mechanism design (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.