Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
This paper introduces "Sample-and-Search," a learning-augmented algorithm for high-dimensional -median clustering that utilizes a predictor to preprocess data, thereby significantly reducing both computational complexity and exponential dimensionality dependency while achieving lower clustering costs compared to state-of-the-art methods.