Cover Image

Relative Error Fair Clustering in the Weak-Strong Oracle Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Braverman, Vladimir, Dharangutte, Prathamesh, Jiang, Shaofeng H. -C., Nguyen, Hoai-An, Wang, Chen, Zhang, Yubo, Zhou, Samson
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fair Clustering in the Sliding Window Model
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
by: Braverman, Vladimir, et al.
Published: (2024)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

Learning-Augmented Hierarchical Clustering
by: Braverman, Vladimir, et al.
Published: (2025)

Coresets for Kernel Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2021)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

Moderate Dimension Reduction for $k$-Center Clustering
by: Jiang, Shaofeng H. -C., et al.
Published: (2023)

Packing Compact Subgraphs with Applications to Districting
by: Chen, Ho-Lin, et al.
Published: (2026)

Local Search for Clustering in Almost-linear Time
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

The Price of Privacy For Approximating Max-CSP
by: Dharangutte, Prathamesh, et al.
Published: (2026)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

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

Improved Algorithms for Clustering with Noisy Distance Oracles
by: Pradhan, Pinki, et al.
Published: (2026)

Sublinear Spectral Clustering Oracle with Little Memory
by: Shen, Ranran, et al.
Published: (2026)

Distributed Algorithms for Euclidean Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Streaming Max-Cut in General Metrics
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Numerical Linear Algebra in Linear Space
by: Liu, Yiping, et al.
Published: (2025)

A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
by: Gribelyuk, Elena, et al.
Published: (2024)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

On Sketching Trimmed Statistics
by: Lin, Honghao, et al.
Published: (2025)

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

Round-efficient Fully-scalable MPC algorithms for k-Means
by: Jiang, Shaofeng H. -C., et al.
Published: (2026)

Near-Optimal Dimension Reduction for Facility Location
by: Huang, Lingxiao, et al.
Published: (2024)

Streaming Algorithms for Geometric Steiner Forest
by: Czumaj, Artur, et al.
Published: (2020)

Tight Analyses of Ordered and Unordered Linear Probing
by: Braverman, Mark, et al.
Published: (2025)

Entrywise Approximate Laplacian Solving
by: Chen, Jingbang, et al.
Published: (2024)

New Oracles and Labeling Schemes for Vertex Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Fair Center Clustering in Sliding Windows
by: Ceccarello, Matteo, et al.
Published: (2025)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
by: Nezhad, Sina Bagheri, et al.
Published: (2025)

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Fair Correlation Clustering Meets Graph Parameters
by: Blaha, Johannes, et al.
Published: (2026)

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
by: Woodruff, David P., et al.
Published: (2024)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Towards Fair Representation: Clustering and Consensus
by: Chakraborty, Diptarka, et al.
Published: (2025)

Metric $k$-clustering using only Weak Comparison Oracles
by: Raychaudhury, Rahul, et al.
Published: (2026)

Fair Submodular Cover
by: Chen, Wenjing, et al.
Published: (2024)