Research map / Learning theory and algorithms / Prediction and decision losses
Dynamic Facility Location in High Dimensional Euclidean Spaces
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 the first fully dynamic facility location algorithm for high-dimensional Euclidean spaces, achieving O(c)-approximation with sublinear amortized update time via a dynamic nearest-neighbor indicator structure and a modified Mettu-Plaxton algorithm.
Problem
Maintaining a high-quality, stable facility location solution under intermixed point insertions and deletions in high-dimensional Euclidean spaces, where prior dynamic methods have linear update time for general metrics or exponential dependence on dimension.
Approach
A near-neighbor indicator data structure built from subsampling and approximate dynamic NN oracles maintains the Mettu-Plaxton radii and a discretized random-priority rule, giving sublinear update time and O(1) recourse via a consistency reduction from prior work.
Key results
- Theorem 1.1: O(c)-approximation with ~O(poly(d) n^{1/c+o(1)}) amortized update time and O(1) amortized recourse in high-dimensional Euclidean spaces.
- Experiments show the dynamic algorithm runs roughly two orders of magnitude faster than re-running Mettu-Plaxton, with objective values very close to MP.
- Amortized recourse stays below 1 on all four datasets in the sliding-window experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dynamic algorithm instead of rerunning the static MP algorithm after updates | Facility location · Twitter, Census1990, KDD-Cup, Covertype | running time: roughly two magnitudes faster | Helped |
| Use the dynamic algorithm instead of the static MP algorithm | Facility location · Twitter, Census1990, KDD-Cup, Covertype | objective value | No clear effect |
| Use the dynamic algorithm | Facility location · Twitter, Census1990, KDD-Cup, Covertype | amortized recourse: less than 1 | Helped |
Surprising findings
- Amortized recourse is below 1 on all datasets, much better than the worst-case bound, attributed to the sliding-window nature of updates.
Limitations
- Worst-case approximation ratio O(c) (O(rho^2) generally) is worse than static constant-factor baselines.
- Experiments use LSH as the approximate NN oracle and a single-machine setup with a sliding window of size 1000.
- Experiments do not apply the consistency reduction, relying on the empirical recourse observation.
Experimental setup
Datasets: Twitter Census1990 Covertype KDD-Cup
Benchmarks: Twitter Census1990 Covertype KDD-Cup
Metrics: objective value amortized recourse running time
Baselines: Mettu-Plaxton (static, re-run per update)
Builds on: Mettu-Plaxton algorithm Czumaj et al. 2024 static facility location algorithm Cohen-Addad et al. 2019 consistent facility location reduction locality-sensitive hashing
Closest papers by meaning
- Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.85)
- Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond (NeurIPS 2025 · similarity 0.85)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.83)
- Fully Dynamic Algorithms for Chamfer Distance (NeurIPS 2025 · similarity 0.83)
- Dynamic Metric Embedding into lp Space (ICML 2024 · similarity 0.83)
- Improved Bounds for Online Facility Location with Predictions (AAAI 2025 · similarity 0.83)
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.