Near-Optimal Dimension Reduction for Facility Location

Oblivious dimension reduction, `a 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 Xsubsetℝd, where facilities can lie in the ambient space (not restricted to X). Our main result is that target dimension m=tildeO(ε-2ddim) 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(ε-2log 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(ε-1log n)^tildeO(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/ε)^tildeO(ddim) d + 2^(1/ε)^tildeO(ddim)) · tildeO(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.