5 papers
Local Search for Clustering in Almost-linear Time
Shaofeng H. -C. Jiang, Yaonan Jin, Jianing Lou +1
We propose the first \emph{local search} algorithm for Euclidean clustering that attains an -approximation in almost-linear time. Specifically, for Euclidean -Means, our a…
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…
Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Yecheng Xue, Xiaoyu Chen, Tongyang Li +1
-Clustering in (e.g., -median and -means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the class…
The Power of Uniform Sampling for -Median
Lingxiao Huang, Shaofeng H. -C. Jiang, Jianing Lou
We study the power of uniform sampling for -Median in various metric spaces. We relate the query complexity for approximating -Median, to a key parameter of the dataset, call…
Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids
T-H. Hubert Chan, Zhiyi Huang, Shaofeng H. -C. Jiang +2
We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm main…