PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering

Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen

arXiv:2609.06384v1cs.LGcs.AI

TL;DR

Fair k-center clustering selects centers from partitioned groups under upper-bound constraints while minimizing the maximum assignment distance. This paper develops parameterized and one-pass streaming algorithms for Euclidean fair k-center, achieving approximation ratios from 2.732 to 4.42 across its settings.

  • Problem

    Fair k-center clustering seeks accurate, fair data summarization by limiting the number of selected centers from each group, while existing sub-5 approximation algorithms are offline or require multiple passes.

  • Method

    The paper develops a fixed-parameter tractable Euclidean fair k-center algorithm and integrates it into one-pass streaming methods, including a polynomial-time variant using network flow techniques.

  • Results

    Approximation ratios are 2.732 offline, 4.464 in one-pass streaming, 2.414 and 3.828 with runtime exponential in k, and 4.732 or 4.42 for polynomial-time one-pass streaming.

  • Takeaways & Limitations

    The polynomial-time one-pass streaming ratio of 4.42 improves upon the previous state-of-the-art ratio of 4.464 in Euclidean space.

  • Takeaways & Limitations

    Experimental results are averaged over 10 runs on 10 simulated datasets, and worst-case instances driving the theoretical guarantees may not arise in the experiments.

Abstract

from arXiv · show

Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further respectively improved to $2.414$ and $3.828$ with a runtime exponential on $k$. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of $4.732$, which can be further improved to $4.42$, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.

1 Introduction

Fair k-center clustering selects centers under per-group upper bounds, and this paper targets the gap between offline Euclidean advances and one-pass streaming practice. It introduces parameterized and polynomial-time streaming algorithms with improved approximation guarantees.

  • Problem setting: Fair k-center limits the number of selected centers from each group while minimizing the maximum assignment distance.The dataset is partitioned into disjoint groups with upper bounds on centers selected from each group.
  • Parameterized algorithms: The first Euclidean FPT fair k-center algorithm achieves a 1 + √3 ≈2.732 approximation ratio.This result is presented as breaking the existing approximation barrier for the Euclidean problem.
  • Research gap: The paper addresses the lack of one-pass streaming algorithms that simultaneously exploit Euclidean geometry and fixed-parameter tractability.Prior algorithms with ratios below 5 were either offline or required multiple passes.
  • Streaming algorithms: A polynomial-time one-pass streaming algorithm achieves 3 + √3 + ϵ ≈4.732 using O(k log α) memory.Here α is the aspect ratio, defined as the maximum divided by minimum pairwise distance.
  • Streaming algorithms: Increasing memory to O(h · k log α) improves the streaming ratio to 4.42, slightly surpassing the prior 4.464 state-of-the-art ratio.The improvement is obtained by setting h = 122.

2 Preliminary

Fair k-center selects k data-point centers while limiting centers from each group, minimizing the maximum assignment distance. The paper uses λ-independent center sets to obtain structural bounds in Euclidean space.

  • The objective minimizes the maximum distance from any data point to its nearest selected center.
  • Fair k-center partitions S into m disjoint groups and imposes upper bounds k_l on centers selected from each group, with total center count k.
  • A λ-independent center set is pairwise more than λ apart while covering every point within distance λ.
  • At most two points of Γ can lie within distance r∗ of any optimal center, implying |Γ| ≤ 2k.
  • When λ = 2r∗, the corresponding center-set bound improves to |Γ| ≤ k.

3 Parameterized and Streaming Algorithms for Euclidean Fair k-Center

The paper develops parameterized offline and streaming algorithms using λ-independent center sets and enumeration. Their guarantees improve Euclidean fair k-center ratios, with exponential dependence on k for the strongest results.

  • Improved ratios: 2.414 is the improved offline ratio, while 3.828 is the resulting improved streaming ratio when runtime is exponential in k.
  • Offline parameterized approximation: The offline algorithm constructs groupwise λ-independent sets, unions them, enumerates fair center sets of size at most k, and selects the smallest-radius set.
  • Offline parameterized approximation: 2.732 is the approximation ratio of the parameterized Euclidean fair k-center algorithm, with runtime O(2^k(1+log m) · mnk^2 log n).
  • Parameterized approximation in streams: The streaming framework maintains λ-independent center sets during one pass and uses enumeration over their union rather than the full data set.
  • Parameterized approximation in streams: 4.464 is the streaming approximation ratio obtained by post-processing groupwise streaming center sets with the parameterized enumeration method.

4 Streaming Euclidean Fair k-Center in Polynomial Runtime

The polynomial-time streaming algorithm combines independent center sets with an auxiliary flow graph to enforce fairness. It achieves a 4.732 ratio and improves it to 4.42 using a smaller threshold.

  • The algorithm constructs one global center set with λ = 2r∗ and groupwise center sets with λ = 3r∗ during streaming.
  • The graph uses unit-capacity source, replacement, and group-membership edges, while edges from group vertices to the target have capacity k_l.
  • A maximal flow in the auxiliary graph corresponds to selecting at most k centers that satisfy group upper bounds and cover S within the target radius.
  • 4.732 is the approximation ratio achieved by the polynomial-runtime one-pass streaming algorithm for general m.
  • 4.42 is obtained by using the smaller threshold λ = 2r∗ for groupwise center sets, slightly improving the previous 4.464 state-of-the-art ratio.

5 Experimental Results

The experiments compare offline and streaming fair k-center algorithms on simulated and real-world datasets using clustering cost, empirical approximation ratio, and runtime. Parameterized methods generally perform strongly, while fairness imbalance and streaming memory constraints affect observed cost and ratios.

  • Datasets and metrics: Experiments use simulated data with known optima and three UCI datasets—Wholesale, Student, and Adult—under varying fairness-group settings.Algorithms are evaluated over multiple runs using clustering cost and runtime.
  • Approximation factor: Offline methods consistently achieve lower empirical approximation ratios than streaming methods as the number of groups increases.The comparison uses |S| = 200, k = 9, and group counts from 2 to 6.
  • Approximation factor: More memory improves streaming performance: imPSA uses more memory than other streaming algorithms and achieves better empirical results.The experiments also note that worst-case instances underlying theoretical guarantees may not appear in the sampled simulations.
  • Approximation factor: Parameterized methods generally outperform the baselines empirically, with OPA strongest offline and imPSA strongest among the streaming methods.The observed ratios remain consistent with the algorithms’ theoretical guarantees when offline and streaming results are analyzed separately.
  • Real-world datasets: The candidate-center restriction can prevent the optimal restricted solution from matching the best solution on the full dataset, especially when k is large.The paper reports this issue particularly for the Adult dataset, where k is about 300 under the stated setting.
  • Robustness: Clustering cost increases as the fairness ratio becomes more unbalanced on the Student dataset.The methods first construct candidate centers without group labels, so candidate coverage is more favorable when fairness ratios match the data distribution.

6 Conclusion

The paper concludes with parameterized offline and streaming algorithms for Euclidean fair k-center, including improved ratios for exponential-in-k methods and a polynomial-time streaming guarantee. The polynomial-time ratio is further improved beyond the prior Euclidean state of the art.

  • Polynomial-time streaming: 4.42 is the further-improved polynomial-time streaming ratio, surpassing the previous Euclidean state-of-the-art ratio of 4.464.The comparison is explicitly made against the prior result due to Guo et al.

A Proof of Lem. 3

This proof bounds a combinatorial expression using Stirling’s approximation and a monotonicity argument. It also identifies an ILP as an exact alternative to enumeration for solving the fair k-center subproblem.

  • Combinatorial bound: Stirling’s approximation transforms the factorial expression into logarithmic terms plus an O(log(2mk)) remainder.The stated approximation is log(n!) = n log n − n log e + O(log n).
  • Monotonicity argument: The proof reduces the remaining bound to showing nonnegativity for a function f(t) for every t ≥ 1.A Taylor-expansion inequality establishes g(t) ≥ 0, which implies f′(t) ≥ 0 and then f(t) ≥ 0.
  • Stage 2 solver: An ILP is presented as a more efficient and elegant exact solver for Stage 2 than enumeration.The variables encode selected centers and assignments, while distances determine feasibility.

C Dealing with Unknown r∗

Because the optimal radius is unknown in streaming, the method replaces it with geometrically spaced candidates maintained in parallel. A modified doubling procedure updates the lower bound and yields a valid independent center set.

  • Unknown optimal radius: The optimal radius r* is assumed known for analysis but must be replaced algorithmically because its exact value is unavailable.The paper first establishes that r* belongs to the set of pairwise distances between input points.
  • Radius candidates: The replacement radii are r_j = L(1 + ε)^j for j ∈ {1, …, t}, using a maintained lower bound L.There are O(t) candidate radii, so the streaming method runs parallel instances using O(tk) = O(k^(1/ε)) memory.
  • Streaming update: The modified doubling algorithm is used because searching all pairwise distances is infeasible in a streaming model.Initially L is the minimum distance among the first k + 1 arriving points and may increase later.
  • Streaming update: When a candidate center set exceeds k centers, the algorithm increases the radius range and recomputes centers with a greedy algorithm on cached and arriving points.The update maintains a sufficiently large first radius and adjusts t and L accordingly.
  • Correctness: For any ε > 0, the minimum-radius candidate center set with at most k centers is λ-independent for λ = (2 + ε)r*.This lemma provides the correctness guarantee for the radius-replacement procedure.

D Better Ratios under Smaller λ

The section shows that decreasing λ improves approximation ratios but increases the size of Γ and memory complexity, while Euclidean packing bounds enable stronger parameterized guarantees.

  • Trade-off: Smaller λ improves the approximation ratio but increases Γ and memory complexity.
  • Geometric bound: The geometric packing property bounds the number of mutually distant points in a δ-dimensional ball and supports the lemma's stronger construction.
  • Geometric bound: At most 4 points can have pairwise distance 4√6r∗ in the relevant three-dimensional ball, yielding O(3k) buffered points when λ = 4√6r∗.

Datasets

The experiments use simulated and real-world datasets with group assignments derived from dataset attributes, and compare algorithm running times against baselines.

  • Datasets: Wholesale3 uses the channel attribute for two group assignments across 440 product records.
  • Datasets: Student uses sex for group assignments across 649 student records, while Adult uses gender across 32,561 individuals.
  • Running time: OPA and imPSA are slower than other methods, PSA has comparable running time to other streaming algorithms, and the online methods are slower than two cited baselines on the small dataset.
Loading 2609.06384v1…