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

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Cheng, Kangke, Song, Shihong, Mo, Guanlin, Ding, Hu
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Machine Learning
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
di: Mo, Guanlin, et al.
Pubblicazione: (2024)

Average Sensitivity of Hierarchical $k$-Median Clustering
di: Li, Shijie, et al.
Pubblicazione: (2025)

Learning Augmented Graph $k$-Clustering
di: Fan, Chenglin, et al.
Pubblicazione: (2025)

Learning-Augmented Algorithms for $k$-median via Online Learning
di: Hebbar, Anish, et al.
Pubblicazione: (2026)

Learning-Augmented Streaming Algorithms for Correlation Clustering
di: Dong, Yinhao, et al.
Pubblicazione: (2025)

A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
di: Makarychev, Konstantin, et al.
Pubblicazione: (2025)

Learning-Augmented Hierarchical Clustering
di: Braverman, Vladimir, et al.
Pubblicazione: (2025)

A Faster $k$-means++ Algorithm
di: Liang, Jiehao, et al.
Pubblicazione: (2022)

On the Power of Learning-Augmented Search Trees
di: Chen, Jingbang, et al.
Pubblicazione: (2022)

Learning-Augmented Search Data Structures
di: Fu, Chunkai, et al.
Pubblicazione: (2024)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
di: Funk, Nicole, et al.
Pubblicazione: (2026)

Learning-Augmented Algorithms with Explicit Predictors
di: Elias, Marek, et al.
Pubblicazione: (2024)

Prediction-Specific Design of Learning-Augmented Algorithms
di: Li, Sizhe, et al.
Pubblicazione: (2025)

Incremental (k, z)-Clustering on Graphs
di: Cruciani, Emilio, et al.
Pubblicazione: (2026)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
di: Angelopoulos, Spyros, et al.
Pubblicazione: (2025)

Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
di: Angelopoulos, Spyros, et al.
Pubblicazione: (2024)

Deterministic $k$-Median Clustering in Near-Optimal Time
di: Costa, Martín, et al.
Pubblicazione: (2025)

Connected k-Median with Disjoint and Non-disjoint Clusters
di: Eube, Jan, et al.
Pubblicazione: (2025)

Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms
di: Lechowicz, Adam, et al.
Pubblicazione: (2023)

Dynamic Consistent $k$-Center Clustering with Optimal Recourse
di: Forster, Sebastian, et al.
Pubblicazione: (2024)

Hierarchical Clustering via Local Search
di: Jowhari, Hossein
Pubblicazione: (2024)

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management
di: Hsieh, Wen-Han, et al.
Pubblicazione: (2026)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
di: Zhu, Yanhui, et al.
Pubblicazione: (2024)

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
di: Veldt, Nate, et al.
Pubblicazione: (2026)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
di: Maity, Binita, et al.
Pubblicazione: (2024)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
di: Axiotis, Kyriakos, et al.
Pubblicazione: (2024)

Optimal Algorithms for Augmented Testing of Discrete Distributions
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2025)

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2026)

Hybrid k-Clustering: Blending k-Median and k-Center
di: Fomin, Fedor V., et al.
Pubblicazione: (2024)

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
di: Grigorescu, Elena, et al.
Pubblicazione: (2024)

A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
di: Grigorescu, Elena, et al.
Pubblicazione: (2024)

On Tradeoffs in Learning-Augmented Algorithms
di: Benomar, Ziyad, et al.
Pubblicazione: (2025)

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
di: Shah, Poojan, et al.
Pubblicazione: (2025)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
di: Hu, Hang, et al.
Pubblicazione: (2022)

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
di: Chowdhury, Agniva, et al.
Pubblicazione: (2024)

Learning-Augmented Algorithms for the Bahncard Problem
di: Zhao, Hailiang, et al.
Pubblicazione: (2024)

Learning-Augmented Algorithms for Boolean Satisfiability
di: Attias, Idan, et al.
Pubblicazione: (2025)