Cover Image

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Funk, Nicole, Hennes, Annika, Hillebrand, Johanna, Sturm, Sarah
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computers and Society Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

On the Hardness of Approximation of the Fair k-Center Problem
by: Thejaswi, Suhas
Published: (2026)

FPT Approximations for Fair $k$-Min-Sum-Radii
by: Carta, Lena, et al.
Published: (2024)

A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
by: Ebbens, Matthijs, et al.
Published: (2024)

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

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

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

Generalizing Fair Top-$k$ Selection: An Integrative Approach
by: Cai, Guangya
Published: (2026)

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)

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

A Quantum Approximation Scheme for k-Means
by: Jaiswal, Ragesh
Published: (2023)

Facility Location and $k$-Median with Fair Outliers
by: Dabas, Rajni, et al.
Published: (2025)

An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
by: Cohen-Addad, Vincent, et al.
Published: (2025)

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

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
by: la Tour, Max Dupré, et al.
Published: (2024)

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

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

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

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

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Logarithmic Approximations for Fair k-Set Selection
by: Li, Shi, et al.
Published: (2025)

An Improved Greedy Approximation for (Metric) $k$-Means
by: Charikar, Moses, et al.
Published: (2026)

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

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
by: Cohen-Addad, Vincent, et al.
Published: (2022)

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

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

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

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

Separating $k$-Median from the Supplier Version
by: Anand, Aditya, et al.
Published: (2024)

Continuous Fairness On Data Streams
by: Ghosh, Subhodeep, et al.
Published: (2026)

Time Fairness in Online Knapsack Problems
by: Lechowicz, Adam, et al.
Published: (2023)

Fairness Implications of Encoding Protected Categorical Attributes
by: Mougan, Carlos, et al.
Published: (2022)

Fairness in Streaming Submodular Maximization over a Matroid Constraint
by: Halabi, Marwa El, et al.
Published: (2023)

A Scalable Algorithm for Individually Fair K-means Clustering
by: Bateni, MohammadHossein, et al.
Published: (2024)

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

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

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

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

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)