🤖 machine learning

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

This paper presents improved constant-factor approximation algorithms for discrete k-clustering problems under doubly constrained fairness (combining group fairness and diverse center selection), achieving a 4-approximation for k-center and proposing the first constant-factor approximations for k-median and k-means using an LP-based transformation approach.

Original authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm

Published 2026-04-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicole Funk, Annika Hennes, Johanna Hillebrand, Sarah Sturm

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive company retreat. You have a list of employees (the data points) and you need to split them into $k$ different groups (clusters) for activities. Each group needs a leader (a center).

Usually, the goal is just to make sure everyone is close to their leader so the groups are tight and efficient. But in the real world, we also care about fairness.

This paper tackles a very specific, tricky version of this problem where we have to satisfy two different types of fairness at the same time. The authors call this "Doubly Constrained Fair Clustering."

Here is the breakdown of the problem and their solution, using simple analogies.

The Two Rules of Fairness

To understand the problem, imagine you are the retreat planner. You have two bosses giving you conflicting instructions:

1. The "Balanced Room" Rule (Group Fairness)
Your first boss says: "Every activity room must have a mix of people. No room can be 90% engineers and 10% marketers. Every room must have a specific percentage of each department."

The Goal: Ensure that inside every cluster, the demographics are balanced according to a set ratio (e.g., 50% men, 50% women, or 40% engineers, 60% designers).

2. The "Diverse Leaders" Rule (Diverse Center Selection)
Your second boss says: "The leaders of these groups must also be diverse. You can't pick 5 leaders who are all from the same department. You need exactly 2 engineers, 2 marketers, and 1 designer as the group leaders."

The Goal: Ensure that the people chosen to lead the groups represent the whole company, not just one slice of it.

The Conflict:
It's easy to satisfy one rule. It's easy to satisfy the other. But doing both at the same time is a nightmare.

If you pick diverse leaders first, you might accidentally put all the "minority" employees into one group to make the leaders happy, violating the "Balanced Room" rule.
If you balance the rooms first, you might end up with a group of 50 people but only one leader from a specific department, violating the "Diverse Leaders" rule.

The Previous Solution (The "Clumsy" Approach)

Before this paper, researchers tried to solve this by doing things one step at a time (sequentially).

Step 1: Find a solution that balances the rooms.
Step 2: Try to tweak it to get diverse leaders.
Result: This was like trying to fix a leaky boat while it's already sinking. The math showed that this approach was "expensive" (in terms of efficiency) and often resulted in a solution that was 8 times worse than the perfect theoretical solution. It was also messy, sometimes breaking the rules slightly.

The New Solution (The "Master Planner" Approach)

The authors of this paper (Funk, Hennes, Hillebrand, and Sturm) came up with a much smarter, more elegant way to do it. They improved the efficiency significantly, making the solution 4 times better for the "k-center" problem (the most basic version) and creating the first-ever efficient solutions for the more complex "k-median" and "k-means" problems.

Here is how their "Master Planner" algorithm works, step-by-step:

Step 1: The "Ghost" Plan (Linear Programming)

First, they don't pick real people yet. They create a fractional, "ghost" plan.

Imagine you can split a person into 0.5 of a person.
They use a computer program (Linear Programming) to figure out how to split everyone up so that the "Balanced Room" rule is perfectly satisfied.
Analogy: It's like a blueprint where the walls are drawn perfectly, but the furniture isn't placed yet.

Step 2: The "Leader" List (Diverse Centers)

Separately, they use a known algorithm to pick the actual leaders (centers) who satisfy the "Diverse Leaders" rule.

Analogy: They hire the specific managers they need (2 engineers, 2 marketers, etc.) before worrying about who sits in their office.

Step 3: The "Rerouting" Dance (The Magic Trick)

This is the most creative part. They have the "Ghost Plan" (balanced rooms) and the "Leader List" (diverse bosses). They need to merge them.

The Problem: The Ghost Plan might have assigned people to leaders who aren't on the Leader List.
The Solution: They perform a mathematical "rerouting."
- Imagine a point $P$ is currently assigned to a "Ghost Leader" $L_{ghost}$ .
- They look at the "Real Leader" $L_{real}$ who is closest to $P$ .
- They move the assignment from $L_{ghost}$ to $L_{real}$ .
- The Catch: They have to be careful not to break the "Balanced Room" rule while moving people. They do this by splitting the "mass" (the people) proportionally. If a room needs 50% engineers, and they move an engineer, they make sure the math still adds up.

Step 4: The Final Assignment (Max Flow)

Finally, they take this messy, fractional plan and turn it into a real, solid plan where every person is assigned to exactly one leader.

They use a "Max Flow" algorithm (think of it like a water pipe system) to ensure that:
1. Every leader gets at least one person (so they aren't empty).
2. The "Balanced Room" rule is still mostly followed (allowing for a tiny, harmless error of 1 or 2 people, which is acceptable in the real world).

Why This Matters

It's Faster and Better: For the simplest problem (k-center), they cut the "badness" of the solution in half (from 8x down to 4x).
It Solves the Unsolvable: For the more complex problems (k-median and k-means), which are used in things like image recognition and customer segmentation, they are the first to provide a guaranteed, efficient solution.
It's Flexible: Their method isn't just for these two rules. It can be adapted to other fairness rules, like ensuring leaders come from specific geographic regions or have specific skills (matroid constraints).

The Bottom Line

Think of this paper as a new, sophisticated recipe for organizing a chaotic party.

Old way: "Let's seat people by color first, then try to pick leaders. Good luck, the room will be a mess."
New way: "Let's draw a perfect blueprint for seating, pick our diverse leaders, and then use a mathematical dance to move people from the blueprint to the leaders without breaking the balance."

The result is a party where everyone is happy, the leaders represent the crowd, and the groups are organized efficiently. The authors proved mathematically that this new recipe works every time, and it's much better than anything we had before.

1. Problem Definition

The paper addresses Doubly Constrained Fair Clustering in general metric spaces. The goal is to partition a set of points $P$ into $k$ clusters, each with a designated center from $P$ , to minimize a standard objective function ( $k$ -center, $k$ -median, or $k$ -means) while satisfying two simultaneous demographic fairness constraints:

Group Fairness (GF): Ensures that within every cluster, the proportion of points belonging to each protected group (color) lies within specified lower ( $\ell_h$ ) and upper ( $u_h$ ) bounds. The paper allows for a small additive violation ( $\rho$ ) of these fractional bounds to achieve constant-factor approximations.
Diverse Center Selection (DS): Ensures that the set of $k$ cluster centers itself is representative. Specifically, the number of centers selected from each protected group must satisfy lower ( $L_h$ ) and upper ( $U_h$ ) bounds.

The Challenge: Previous work (Dickerson et al., 2023) addressed this by sequentially solving the two constraints, resulting in approximation factors that depended on the product of the individual approximation factors (e.g., an 8-approximation for $k$ -center). This paper aims to improve these factors and, crucially, provide the first constant-factor approximations for the doubly constrained $k$ -median and $k$ -means problems.

2. Methodology

The authors propose a unified framework for all three objectives ( $k$ -center, $k$ -median, $k$ -means) that combines a Linear Programming (LP) approach with a rerouting technique inspired by flow networks. The algorithm proceeds in four main steps:

Step 1: Independent Solutions

Diverse Centers ( $C_{DS}$ ): An existing "opaque-box" approximation algorithm is used to compute a set of centers $C_{DS}$ that satisfies the DS constraint. Let $\gamma$ be the approximation factor of this subroutine.
Fractional Group Fair Solution: A Linear Program (LP) is solved to find a fractional assignment $(x, y)$ that satisfies the Group Fairness (GF) constraints and minimizes the objective (or bounds the radius for $k$ -center). This solution allows points to be fractionally assigned to multiple centers.

Step 2: Mass Rerouting (The Core Innovation)

The fractional solution $(x, y)$ may use centers not in $C_{DS}$ . The algorithm reroutes the "mass" (assignments) from the LP solution to the diverse centers $C_{DS}$ while preserving the group fairness properties.

Mechanism: For a point $p$ $p$ receiving mass in the LP solution, the algorithm checks if $p$ $p$ is in the neighborhood of any center in $C_{DS}$ $C_{D S}$ .
- If $p$ is near a diverse center, the incoming mass is split proportionally among the diverse centers in $C_{DS}$ that are close to $p$ .
- If $p$ is not near any diverse center, the mass is rerouted to the nearest center in $C_{DS}$ .
Handling Lower Bounds: A key technical contribution is ensuring that every center in $C_{DS}$ receives at least one unit of mass (to remain active). The rerouting logic is designed to guarantee that no center in $C_{DS}$ is left empty, even if the original LP solution did not assign mass to it directly.

Step 3: Integral Rounding

The result of Step 2 is a new fractional solution $(x', y')$ that satisfies both DS and GF constraints but is still fractional.

$k$ -Center: The fractional assignment is converted to an integral one by solving a Max-Flow problem with lower bounds on edge capacities.
$k$ -Median/ $k$ -Means: The fractional assignment is converted using a Min-Cost Flow formulation.
Rounding Error: This rounding step introduces an additive violation of at most 2 to the group fairness constraints (i.e., the bounds $\ell_h$ and $u_h$ are violated by at most 2 points per cluster).

3. Key Contributions

Improved $k$ -Center Approximation:
- Previous best: 8-approximation (Dickerson et al.).
- New Result: 4-approximation with an additive GF violation of $\le 2$ .
- This is achieved by combining the best known DS-fair $k$ -center algorithm (3-approx) with the authors' rerouting framework, yielding a factor of $\gamma_{center} + 1 = 3 + 1 = 4$ .
First Constant-Factor Approximations for $k$ -Median and $k$ -Means:
- Prior to this work, no constant-factor approximations existed for doubly constrained $k$ -median or $k$ -means in general metrics.
- $k$ -Median Result: 10.081-approximation (using the 7.081-approx for DS-fair median).
- $k$ -Means Result: $\approx 325.06$ -approximation (using the 256-approx for DS-fair means).
- For Euclidean $k$ -means, the factor improves to $\approx 101.11$ .
Generalizability:
- The framework is modular. The "opaque-box" nature of the center selection step allows the algorithm to be applied to other center constraints, such as matroid constraints or knapsack constraints, provided a corresponding approximation algorithm exists.

4. Results Summary

Objective	Previous Best (Dickerson et al.)	This Work (Approx. Ratio)	Additive GF Violation
$k$ -Center	8	4	$\le 2$
$k$ -Median	$O(\Delta)$ (Dependent on cluster size)	10.081	$\le 2$
$k$ -Means	$O(\sqrt{\Delta})$	$\approx 325.06$	$\le 2$

Note: $\Delta$ represents the maximum cluster size in the solution.

5. Significance

Theoretical Breakthrough: This paper resolves the open problem of finding constant-factor approximations for doubly constrained fair clustering for $k$ -median and $k$ -means, which were previously only solvable with factors dependent on cluster sizes or via FPT algorithms.
Practical Relevance: By reducing the approximation factor for $k$ -center from 8 to 4, the paper provides significantly tighter bounds for practical applications where both representative centers and balanced cluster compositions are required (e.g., diverse committee selection, equitable resource allocation).
Algorithmic Framework: The proposed "rerouting" technique offers a robust method for combining disparate fairness constraints. It demonstrates how to merge a solution satisfying one constraint (diverse centers) with a fractional solution satisfying another (group fairness) without losing the approximation guarantees of the underlying subroutines.
Trade-off Analysis: The results highlight a trade-off between strict fairness (zero violation) and approximation quality. The authors achieve constant factors by allowing a small, bounded additive violation (2 points) in group fairness, which is often acceptable in real-world scenarios compared to the exponential or size-dependent factors of previous methods.

In conclusion, the paper establishes a new state-of-the-art for fair clustering under multiple constraints, providing the first constant-factor guarantees for the most common clustering objectives ( $k$ -median, $k$ -means) and significantly improving the bounds for $k$ -center.