4 papers
A Fast and Simple -Approximation for Minimum Spanning Trees in Doubling Metrics
Jan Höckendorff, Felix Hommelsheim, Christian Sohler +1
The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a -approximation to the…
Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
Anne Driemel, Jan Höckendorff, Ioannis Psarros +2
Given a finite metric space the -median problem is to find a set of centers that minimizes $\sum_{p\in X} \min_{c\in C} \mathbf{d}(p,c…
Dimension Reduction for Clustering: The Curious Case of Discrete Centers
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir +2
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of points into dimension with low…
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…