Fair Colorful k-Center Clustering

Xinrui Jia, Kshiteej Sheth, Ola Svensson

Abstract

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius $\rho$ such that there exist balls of radius $\rho$ around k of the points that meet the coverage requirements. This problem combines the difficulties of clustering with the subset-sum problem, leading to strong integrality gap lower bounds for natural linear programming relaxations. We present an efficient 3-approximation algorithm that overcomes these difficulties, nearly matching the tight 2-approximation for the classical k-center problem.

Introduction

The classic $k$-center problem seeks to select $k$ centers to minimize the maximum distance from any data point to its nearest center. Real-world applications often require more nuance, such as $k$-center with outliers, which allows for a subset of points to remain uncovered. The colorful $k$-center problem further generalizes this by introducing fairness constraints: the selected clusters must cover at least $r$ "red" points and $b$ "blue" points.

This problem is significantly more challenging than its predecessors because it implicitly embeds a subset-sum problem. Selecting $k$ centers requires satisfying global color quotas, which depends on the specific number of red and blue points within each individual cluster. Standard Linear Programming (LP) relaxations fail to capture this combinatorial complexity, often leading to unbounded integrality gaps.

Methodology

The proposed algorithm achieves a 3-approximation by decoupling the spatial clustering from the subset-sum constraints through a multi-phase approach.

Phase I: Guessing and Partitioning

The algorithm begins by "guessing" a small number of centers from the optimal solution. This step is performed by iterating through a polynomial number of possibilities, allowing the algorithm to establish bounds on the color distribution within clusters. Subsequently, the dataset is partitioned into "dense" regions (with high color concentrations) and "sparse" regions.

Phase II: Decoupled Solving

The problem is then solved separately for each partition:

  1. Dense Set: Clustering in dense regions is reduced to a 3-dimensional subset-sum problem, which is solved exactly using Dynamic Programming (DP).
  2. Sparse Set: For sparse regions, the algorithm employs a pseudo-approximation LP rounding technique. By removing dense clusters, the LP is no longer susceptible to the subset-sum "traps" that typically cause it to fail.
Geometric configurations illustrating the spatial relationships between centers and points in the approximation analysis.

Integrality Gap Analysis

A key contribution of the paper is the formal proof that standard LP relaxations have an unbounded integrality gap. The authors demonstrate that even advanced techniques like the Sum-of-Squares (SoS) hierarchy or specialized network flow constraints cannot resolve the infeasibility of fractional solutions when the subset-sum structure is present.

Linear programming relaxations LP1 and LP2 used to model the colorful k-center problem.

Key Insights

  • The Subset-Sum Sabotage: The core difficulty of colorful $k$-center lies in its equivalence to finding a subset of cluster coverage values that sum to exact quotas. The authors show that a radius-1 ball can contain $A \pm a_i$ points, making the feasibility check as hard as the subset-sum problem.
  • Limitations of Automated Tightening: The failure of $\Omega(n)$ rounds of the Lasserre/Sum-of-Squares hierarchy is a significant theoretical result, showing that even powerful automated relaxation strengtheners cannot "see" the subset-sum constraint.
  • Density-Based Isolation: By isolating dense points for DP and using LP rounding only for sparse points, the algorithm prevents the LP from being "confused" by the hard combinatorial constraints of the dense regions.

Key Results

The primary result is a 3-approximation algorithm for the colorful $k$-center problem with two colors. This guarantee ensures that the radius found is at most three times the optimal radius. The algorithm generalizes to $\omega$ color classes with a runtime of $n^{O(\omega^2)}$, making it efficient for a constant number of groups. Furthermore, the paper establishes rigorous lower bounds on the performance of standard LP relaxations.

Conclusion and Future Work

While the 3-approximation is a major step forward, a gap remains between this result and the 2-approximation limit of the classic $k$-center problem. Future research may focus on closing this gap or exploring whether a combination of SoS hierarchies and flow constraints could finally bridge the integrality gap. Additionally, improving the algorithm's scaling with the number of color classes remains an important open challenge for large-scale fairness applications.

Summary updated

Abstract

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius \r{ho} such that there exist balls of radius \r{ho} around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes.
BibTeX
@article{jia2022fair,
  author = {Xinrui Jia and Kshiteej Sheth and Ola Svensson},
  title = {{Fair Colorful k-Center Clustering}},
  journal = {Math. Program.},
  year = {2022},
  doi = {10.1007/s10107-021-01674-7},
}

Loading related content...

Figure