Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions

• URL: http://arxiv.org/abs/2603.10721v1
• Date: Wed, 11 Mar 2026 12:53:33 GMT
• Title: Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
• Abstract summary: We introduce an algorithm for this problem based on a simple yet effective sampling method.<n>We conduct experiments to compare our method with several state-of-the-art learning-augmented $k$-median clustering methods.
• Score: 18.61347737579578
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $α\in [0,1)$. This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented $k$-median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.

Related papers

• CavMerge: Merging K-means Based on Local Log-Concavity [2.579311291240392]
  K-means clustering is known to exhibit suboptimal performance when applied to non-linearly separable data.<n>We present emphCavMerge, a novel K-means merging algorithm that is intuitive, free of parameter tuning, and computationally efficient.
  arXiv  Detail & Related papers  (2026-04-05T22:47:36Z)
• Average Sensitivity of Hierarchical $k$-Median Clustering [9.107341310040155]
  We focus on the hierarchical $k$ -median clustering problem, which bridges hierarchical and centroid-based clustering.<n>We propose an efficient algorithm for hierarchical $k$-median clustering and theoretically prove its low average sensitivity and high clustering quality.
  arXiv  Detail & Related papers  (2025-07-14T14:02:31Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• Unsupervised Machine Learning to Classify the Confinement of Waves in Periodic Superstructures [0.0]
  We employ unsupervised machine learning to enhance the accuracy of our recently presented scaling method for wave confinement analysis. We employ the standard k-means++ algorithm as well as our own model-based algorithm. We find that the clustering approach provides more physically meaningful results, but may struggle with identifying the correct set of confinement dimensionalities.
  arXiv  Detail & Related papers  (2023-04-24T08:22:01Z)
• Rethinking Clustering-Based Pseudo-Labeling for Unsupervised Meta-Learning [146.11600461034746]
  Method for unsupervised meta-learning, CACTUs, is a clustering-based approach with pseudo-labeling. This approach is model-agnostic and can be combined with supervised algorithms to learn from unlabeled data. We prove that the core reason for this is lack of a clustering-friendly property in the embedding space.
  arXiv  Detail & Related papers  (2022-09-27T19:04:36Z)
• Gradient Based Clustering [72.15857783681658]
  We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions.
  arXiv  Detail & Related papers  (2022-02-01T19:31:15Z)
• Envelope Imbalance Learning Algorithm based on Multilayer Fuzzy C-means Clustering and Minimum Interlayer discrepancy [14.339674126923903]
  This paper proposes a deep instance envelope network-based imbalanced learning algorithm with the multilayer fuzzy c-means (MlFCM) and a minimum interlayer discrepancy mechanism based on the maximum mean discrepancy (MIDMD) This algorithm can guarantee high quality balanced instances using a deep instance envelope network in the absence of prior knowledge.
  arXiv  Detail & Related papers  (2021-11-02T04:59:57Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)
• Fair Correlation Clustering [92.15492066925977]
  We obtain approximation algorithms for correlation clustering under several important types of fairness constraints. We show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.
  arXiv  Detail & Related papers  (2020-02-06T14:28:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.