Buchumschlag

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Shah, Poojan, Agrawal, Shashwat, Jaiswal, Ragesh
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Machine Learning
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Fast $k$-means Seeding Under The Manifold Hypothesis
von: Shah, Poojan, et al.
Veröffentlicht: (2026)

Quantum (Inspired) $D^2$-sampling with Applications
von: Shah, Poojan, et al.
Veröffentlicht: (2024)

A Quantum Approximation Scheme for k-Means
von: Jaiswal, Ragesh
Veröffentlicht: (2023)

Improved Algorithms for Clustering with Noisy Distance Oracles
von: Pradhan, Pinki, et al.
Veröffentlicht: (2026)

Clustering What Matters in Constrained Settings
von: Jaiswal, Ragesh, et al.
Veröffentlicht: (2023)

Robust-Sorting and Applications to Ulam-Median
von: Jaiswal, Ragesh, et al.
Veröffentlicht: (2025)

FPT Approximation for Capacitated Sum of Radii
von: Jaiswal, Ragesh, et al.
Veröffentlicht: (2024)

A Faster $k$-means++ Algorithm
von: Liang, Jiehao, et al.
Veröffentlicht: (2022)

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
von: Cheng, Kangke, et al.
Veröffentlicht: (2026)

On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
von: Kalavasis, Alkis, et al.
Veröffentlicht: (2024)

Mini-Batch Kernel $k$-means
von: Jourdan, Ben, et al.
Veröffentlicht: (2024)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
von: Angelopoulos, Spyros, et al.
Veröffentlicht: (2025)

Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
von: Song, Shihong, et al.
Veröffentlicht: (2024)

Learning Augmented Graph $k$-Clustering
von: Fan, Chenglin, et al.
Veröffentlicht: (2025)

Incremental (k, z)-Clustering on Graphs
von: Cruciani, Emilio, et al.
Veröffentlicht: (2026)

Dynamic algorithms for k-center on graphs
von: Cruciani, Emilio, et al.
Veröffentlicht: (2023)

Statistical-Computational Trade-offs for Density Estimation
von: Aamand, Anders, et al.
Veröffentlicht: (2024)

$k$NN Attention Demystified: A Theoretical Exploration for Scalable Transformers
von: Haris, Themistoklis
Veröffentlicht: (2024)

Sample-Adaptivity Tradeoff in On-Demand Sampling
von: Haghtalab, Nika, et al.
Veröffentlicht: (2025)

Average Sensitivity of Hierarchical $k$-Median Clustering
von: Li, Shijie, et al.
Veröffentlicht: (2025)

Generalized Top-k Mallows Model for Ranked Choices
von: Haddadan, Shahrzad, et al.
Veröffentlicht: (2025)

Dynamic Consistent $k$-Center Clustering with Optimal Recourse
von: Forster, Sebastian, et al.
Veröffentlicht: (2024)

Stochastic $k$-Submodular Bandits with Full Bandit Feedback
von: Nie, Guanyu, et al.
Veröffentlicht: (2024)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
von: Zhu, Yanhui, et al.
Veröffentlicht: (2024)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
von: Drexler, Lukas, et al.
Veröffentlicht: (2023)

Metric $k$-clustering using only Weak Comparison Oracles
von: Raychaudhury, Rahul, et al.
Veröffentlicht: (2026)

Learning-Augmented Algorithms for $k$-median via Online Learning
von: Hebbar, Anish, et al.
Veröffentlicht: (2026)

Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
von: Chen, Tyler, et al.
Veröffentlicht: (2025)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
von: He, Yuchen, et al.
Veröffentlicht: (2024)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
von: Makarychev, Konstantin, et al.
Veröffentlicht: (2025)

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
von: Zhang, Guangyi, et al.
Veröffentlicht: (2026)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
von: Maity, Binita, et al.
Veröffentlicht: (2024)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
von: Oettershagen, Lutz
Veröffentlicht: (2026)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
von: Krivošija, Amer, et al.
Veröffentlicht: (2025)

Polynomial-time derivation of optimal k-tree topology from Markov networks
von: Dastjerdi, Fereshteh R., et al.
Veröffentlicht: (2024)

Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
von: Rohatgi, Dhruv, et al.
Veröffentlicht: (2025)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
von: Chowdhury, Agniva, et al.
Veröffentlicht: (2024)

Learning general Gaussian mixtures with efficient score matching
von: Chen, Sitan, et al.
Veröffentlicht: (2024)

Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions
von: Qin, Yilong, et al.
Veröffentlicht: (2023)

Thompson Sampling Itself is Differentially Private
von: Ou, Tingting, et al.
Veröffentlicht: (2024)