Near-Optimal Dimension Reduction for Facility Location

Oblivious dimension reduction, à la the Johnson-Lindenstrauss (JL) Lemma, is a fundamental approach for processing high-dimensional data. We study this approach for Uniform Facility Location (UFL) on a Euclidean input X ⊂ R d , where facilities can lie in the ambient space (not restricted to X). Our main result is that target dimension m = Õ(ε -2 ddim) suffices to (1+ε)-approximate the optimal value of UFL on inputs whose doubling dimension is bounded by ddim. It significantly improves over previous results, that could only achieve O(1)-approximation [Narayanan, Silwal, Indyk, and Zamir, ICML 2021] or dimension m = O(ε -2 log n) for n = |X|, which follows from [Makarychev, Makarychev, and Razenshteyn, STOC 2019]. Our oblivious dimension reduction has immediate implications to streaming and offline algorithms, by employing known algorithms for low dimension. In dynamic geometric streams, it implies a (1 + ε)-approximation algorithm that uses O(ε -1 log n) Õ(ddim/ε 2 ) bits of space, which is the first streaming algorithm for UFL to utilize the doubling dimension. In the offline setting, it implies a (1 + ε)-approximation algorithm, which we further refine to run in time ((1/ε) Õ(ddim) d + 2 (1/ε) Õ(ddim) ) • Õ(n). Prior work has a similar running time but requires some restriction on the facilities [Cohen-Addad, Feldmann and Saulpic, JACM 2021]. Our main technical contribution is a fast procedure to decompose an input X into several k-median instances for small k. This decomposition is inspired by, but has several significant differences from [Czumaj, Lammersen, Monemizadeh and Sohler, SODA 2013], and is key to both our dimension reduction and our PTAS.