Near-Optimal Dimension Reduction for Facility Location

Lingxiao Huang, Shaofeng H. -C. Jiang, Robert Krauthgamer +1

Oblivious dimension reduction, à la the Johnson-Lindenstrauss (JL) Lemma, is a fundamental approach for processing high-dimensional data. We study this approach for Uniform Facilit…