Cover Image

Metric $k$-clustering using only Weak Comparison Oracles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Raychaudhury, Rahul, Esmailpour, Aryan, Galhotra, Sainyam, Sintos, Stavros
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Theoretical Framework for Distribution-Aware Dataset Search
by: Esmailpour, Aryan, et al.
Published: (2025)

Faster Relational Algorithms Using Geometric Data Structures
by: Esmailpour, Aryan, et al.
Published: (2026)

Improved Approximation Algorithms for Relational Clustering
by: Esmailpour, Aryan, et al.
Published: (2024)

Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation
by: Shahbazi, Nima, et al.
Published: (2026)

Range (Rényi) Entropy Queries and Partitioning
by: Esmailpour, Aryan, et al.
Published: (2023)

Faster Algorithms for Fair Max-Min Diversification in $\mathbb{R}^d$
by: Kurkure, Yash, et al.
Published: (2024)

Fair Set Cover
by: Dehghankar, Mohsen, et al.
Published: (2024)

Computing Data Distribution from Query Selectivities
by: Agarwal, Pankaj K., et al.
Published: (2024)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
by: Oettershagen, Lutz
Published: (2026)

Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor
by: Shahbazi, Nima, et al.
Published: (2025)

On Fair Epsilon Net and Geometric Hitting Set
by: Dehghankar, Mohsen, et al.
Published: (2025)

A Fair and Memory/Time-efficient Hashmap
by: Asudeh, Abolfazl, et al.
Published: (2023)

Clustering with Set Outliers and Applications in Relational Clustering
by: Surianarayanan, Vaishali, et al.
Published: (2025)

Connectivity Oracles for Predictable Vertex Failures
by: Hu, Bingbing, et al.
Published: (2023)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

Accelerating Matroid Optimization through Fast Imprecise Oracles
by: Eberle, Franziska, et al.
Published: (2024)

Improved and Oracle-Efficient Online $\ell_1$-Multicalibration
by: Ghuge, Rohan, et al.
Published: (2025)

Fast White-Box Adversarial Streaming Without a Random Oracle
by: Feng, Ying, et al.
Published: (2024)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
by: Attias, Idan, et al.
Published: (2025)

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

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

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

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

Dynamic algorithms for k-center on graphs
by: Cruciani, Emilio, et al.
Published: (2023)

Weak to Strong Learning from Aggregate Labels
by: Makhija, Yukti, et al.
Published: (2024)

The Many Faces of Optimal Weak-to-Strong Learning
by: Høgsgaard, Mikael Møller, et al.
Published: (2024)

Parsimonious Learning-Augmented Online Metric Matching
by: Shin, Yongho, et al.
Published: (2026)

$O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
by: Vaze, Rahul, et al.
Published: (2025)

Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost
by: Vaze, Rahul, et al.
Published: (2024)

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

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

Label-consistent clustering for evolving data
by: Gadekar, Ameet, et al.
Published: (2025)

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

Stochastic $k$-Submodular Bandits with Full Bandit Feedback
by: Nie, Guanyu, et al.
Published: (2024)

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

Generalized Top-k Mallows Model for Ranked Choices
by: Haddadan, Shahrzad, et al.
Published: (2025)

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

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

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)