Approximation algorithms for k-median with lower-bound constraints

Ameet Gadekar, Bruno Ordozgoiti, Suhas ThejaswiarXiv 2021 · arXiv · OpenReview

Abstract

We study a variant of classical clustering formulations in the context of algorithmic fairness, known as diversity-aware clustering. In this variant we are given a collection of facility subsets, and a solution must contain at least a specified number of facilities from each subset while simultaneously minimizing the clustering objective ($k$-median or $k$-means). We investigate the fixed-parameter tractability of these problems and show several negative hardness and inapproximability results, even when we afford exponential running time with respect to some parameters. Motivated by these results we identify natural parameters of the problem, and present fixed-parameter approximation algorithms with approximation ratios $(1 + \frac{2}{e} +\epsilon)$ and $(1 + \frac{8}{e}+ \epsilon)$ for diversity-aware $k$-median and diversity-aware $k$-means respectively, and argue that these ratios are essentially tight assuming the gap-exponential time hypothesis. We also present a simple and more practical bicriteria approximation algorithm with better running time bounds. We finally propose efficient and practical heuristics. We evaluate the scalability and effectiveness of our methods in a wide variety of rigorously conducted experiments, on both real and synthetic data.

Introduction

In traditional clustering problems like $k$-median or $k$-means, the objective is to select $k$ centers to minimize the total distance to all other data points. However, when these centers represent critical resources—such as a representative committee or service locations—fairness and diversity constraints become essential. Diversity-aware clustering addresses this by requiring that the chosen centers satisfy specific representation requirements, such as a minimum number of facilities from different demographic groups.

While standard $k$-median is NP-hard, finding a feasible solution is trivial. In contrast, for diversity-aware clustering, even finding a set of centers that satisfies the requirements is NP-complete. This paper explores the problem through the lens of parameterized complexity, asking if efficient solutions exist when the number of clusters ($k$) and the number of attributes ($t$) are small.

Methodology

The authors bridge the gap between theoretical hardness and practical utility using a multi-pronged approach:

  1. FPT Approximation Algorithms: They develop algorithms for Div-$k$-Med and Div-$k$-Means achieving approximation ratios of $(1 + \frac{2}{e} + \epsilon)$ and $(1 + \frac{8}{e} + \epsilon)$, respectively. This involves using coresets to reduce client sets, enumerating constraint patterns across attribute combinations, and framing facility selection as submodular optimization subject to matroid constraints.
  2. Bicriteria Approximation: To improve speed, they propose an algorithm that relaxes the budget, potentially opening up to $2k$ facilities to achieve a $(3+\epsilon)$ approximation.
  3. Practical Heuristics: They introduce a Linear Programming (LP) approach with randomized rounding and a Local Search (LS1) heuristic designed for partition matroid constraints.
  4. Dynamic Programming (DP): A specialized DP to solve the "requirement satisfiability" problem (finding a feasible set of centers) significantly faster than exhaustive search.

Experimental Evaluation

The researchers evaluated their methods on synthetic data to test scalability and on 17 real-world datasets from the UCI Machine Learning Repository (e.g., bank-full, census), using attributes like gender, race, and age to define diversity groups.

Scalability and Efficiency

The proposed heuristics demonstrate strong scalability. In experiments, the methods successfully handled instances with up to 100 million facilities in less than an hour on standard hardware, provided $k$ and $t$ remained small. Figure 6 illustrates this trend, showing runtime performance as the number of facilities $|U|$ increases.

Scalability of the proposed methods with respect to the number of facilities $|U|$.

Feasibility and Group Constraints

A key insight is that the primary bottleneck in practice is often finding a feasible set of centers rather than the clustering itself. The authors' DP approach for feasibility significantly outperforms exhaustive search (ES) as the number of groups $t$ increases. Interestingly, the LP-based heuristic proved highly effective and fast on real-world data, often finding feasible solutions where randomized rounding usually struggles.

Runtime comparison of feasibility algorithms (LP, ES, DP) as the number of groups $t$ increases.

Conclusion

This work establishes that while diversity-aware clustering is theoretically more challenging than standard clustering, the "FPT landscape" is surprisingly similar. By accepting runtimes exponential in $k$ and $t$, one can achieve tight approximation ratios. Practically, the proposed DP and LP-based heuristics enable these fair clustering models to scale to massive datasets, providing a robust framework for diversity-aware resource allocation.

Summary updated

Abstract

We study a variant of classical clustering formulations in the context of algorithmic fairness, known as diversity-aware clustering. In this variant we are given a collection of facility subsets, and a solution must contain at least a specified number of facilities from each subset while simultaneously minimizing the clustering objective ($k$-median or $k$-means). We investigate the fixed-parameter tractability of these problems and show several negative hardness and inapproximability results, even when we afford exponential running time with respect to some parameters. Motivated by these results we identify natural parameters of the problem, and present fixed-parameter approximation algorithms with approximation ratios $\big(1 + \frac{2}{e} +\epsilon \big)$ and $\big(1 + \frac{8}{e}+ \epsilon \big)$ for diversity-aware $k$-median and diversity-aware $k$-means respectively, and argue that these ratios are essentially tight assuming the gap-exponential time hypothesis. We also present a simple and more practical bicriteria approximation algorithm with better running time bounds. We finally propose efficient and practical heuristics. We evaluate the scalability and effectiveness of our methods in a wide variety of rigorously conducted experiments, on both real and synthetic data.
BibTeX
@misc{gadekar2021approximation,
  author = {Ameet Gadekar and Bruno Ordozgoiti and Suhas Thejaswi},
  title = {{Approximation algorithms for k-median with lower-bound constraints}},
  year = {2021},
  eprint = {2112.07030},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.07030},
}
Figure