Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High Dimensions
In this paper, we investigate the learning-augmented k-median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate α ∈ [0,1). This preprocessing step assigns potential labels to the points before