FPT Approximation for Constrained Metric k-Median/Means

Dishant Goyal, Ragesh Jaiswal, Amit Kumar

Introduction

Clustering is a cornerstone of data science, traditionally focused on minimizing the "service cost" of assigning clients to $k$ facilities. In the classic $k$-median problem, the goal is to minimize the sum of distances between clients and their nearest centers; in $k$-means, the objective is the sum of squared distances. While these unconstrained versions are well-studied, real-world scenarios frequently introduce complex operational, privacy, or fairness constraints.

Problem Landscape

Many practical applications require clustering solutions that adhere to specific rules. For example, $r$-gather clustering ensures anonymity by requiring a minimum number of members per cluster, while capacitated clustering limits the load on any single facility. Other variants include $l$-diversity for privacy and chromatic clustering for resource allocation.

Table 1: Definitions of various constrained k-service problems addressed in the paper.

These constrained versions are significantly more challenging than their unconstrained counterparts. Many lack constant-factor approximation algorithms in general metric spaces. Furthermore, unconstrained clustering is known to be $W[2]$-hard when parameterized by $k$, suggesting that finding optimal solutions is computationally infeasible as the number of clusters grows, even for small datasets. This paper addresses these challenges through the framework of Fixed-Parameter Tractable (FPT) approximation.

Methodology: The List-then-Partition Framework

The authors propose a unified "List-then-Partition" strategy to tackle diverse constraints:

  1. The List $k$-service Problem: Instead of searching for a single optimal set of $k$ centers, the algorithm generates a compact list of candidate center sets. The key guarantee is that, with high probability, at least one set in this list provides a good approximation for any feasible clustering under the given constraints.
  2. Partition Algorithms: Once a candidate set of centers is identified, a "partition algorithm" handles the task of assigning clients to these centers. This step ensures that specific constraints (like minimum cluster size or color diversity) are satisfied while minimizing the service cost.

The primary technical contribution is a novel $D^\ell$-sampling algorithm used to construct the candidate list. Starting from a rough initial approximation, the algorithm iteratively samples new points from the client set with probabilities proportional to their current service costs. This approach, inspired by $k$-means++ seeding, is specifically adapted for the FPT setting in general metric spaces.

Key Insights

  • Unified Framework: By decoupling center selection from client assignment, the authors provide a "master key" for constrained clustering. Any problem with an efficient partition algorithm can now leverage this framework for a constant-factor FPT approximation.
  • Metric Space Versatility: Unlike much previous research restricted to Euclidean space ($\mathbb{R}^d$), this work proves that constant-factor approximations are achievable in any metric space. This is vital for applications involving graph-based or non-vectorial data.
  • Leveraging FPT Complexity: By allowing the runtime to be exponential in $k$ but strictly linear in the number of points $n$, the authors bypass traditional polynomial-time hardness barriers.
  • Streaming Compatibility: The sampling-based nature of the algorithm allows it to be implemented as a constant-pass, log-space streaming algorithm, making it suitable for large-scale data processing.

Key Results and Comparative Performance

The paper establishes several new state-of-the-art approximation guarantees. Notably, it provides the first constant-factor approximations for chromatic, $l$-diversity, and semi-supervised $k$-median/means problems.

Table 2: Comparison of approximation factors for various k-service problems. The new FPT results provide significant improvements and first-of-their-kind bounds.

As shown in the table above, the framework achieves a $(3 + \epsilon)$-approximation for general constrained $k$-median and a $(9 + \epsilon)$-approximation for $k$-means. In the special case where facilities must be located at client positions, these bounds improve to $(2 + \epsilon)$ and $(4 + \epsilon)$, respectively. The results also outperform previous bounds for $r$-gather, fault-tolerant, and uncertain clustering variants.

Limitations and Future Directions

While the achieved constant factors are a significant theoretical step, they remain higher than the $(1+\epsilon)$ PTAS available for Euclidean spaces. The authors' synthetic "bad instance" construction suggests that breaking the $(3+\epsilon)$ and $(9+\epsilon)$ barriers in general metric spaces may require techniques more sophisticated than $D^\ell$-sampling. Future research could explore broader constraint types, such as emerging fairness definitions, or seek to further tighten these approximation bounds within the FPT paradigm.

Summary updated

Abstract

The Metric k-median problem over a metric space (𝒳, d) is defined as follows: given a set L ⊆ 𝒳 of facility locations and a set C ⊆ 𝒳 of clients, open a set F ⊆ L of k facilities such that the total service cost, defined as Φ(F, C) := ∑_{x ∈ C} min_{f ∈ F} d(x, f), is minimised. The metric k-means problem is defined similarly using squared distances (i.e., d²(., .) instead of d(., .)). In many applications there are additional constraints that any solution needs to satisfy. For example, to balance the load among the facilities in resource allocation problems, a capacity u is imposed on every facility. That is, no more than u clients can be assigned to any facility. This problem is known as the capacitated k-means/k-median problem. Likewise, various other applications have different constraints, which give rise to different constrained versions of the problem such as r-gather, fault-tolerant, outlier k-means/k-median problem. Surprisingly, for many of these constrained problems, no constant-approximation algorithm is known. Moreover, the unconstrained problem itself is known [Marek Adamczyk et al., 2019] to be W[2]-hard when parameterized by k. We give FPT algorithms with constant approximation guarantee for a range of constrained k-median/means problems. For some of the constrained problems, ours is the first constant factor approximation algorithm whereas for others, we improve or match the approximation guarantee of previous works. We work within the unified framework of Ding and Xu [Ding and Xu, 2015] that allows us to simultaneously obtain algorithms for a range of constrained problems. In particular, we obtain a (3+ε)-approximation and (9+ε)-approximation for the constrained versions of the k-median and k-means problem respectively in FPT time. In many practical settings of the k-median/means problem, one is allowed to open a facility at any client location, i.e., C ⊆ L. For this special case, our algorithm gives a (2+ε)-approximation and (4+ε)-approximation for the constrained versions of k-median and k-means problem respectively in FPT time. Since our algorithm is based on simple sampling technique, it can also be converted to a constant-pass log-space streaming algorithm. In particular, here are some of the main highlights of this work: 1) For the uniform capacitated k-median/means problems our results matches previously known results of Addad et al. [Vincent Cohen-Addad and Jason Li, 2019]. 2) For the r-gather k-median/means problem (clustering with lower bound on the size of clusters), our FPT approximation bounds are better than what was previously known. 3) Our approximation bounds for the fault-tolerant, outlier, and uncertain versions is better than all previously known results, albeit in FPT time. 4) For certain constrained settings such as chromatic, l-diversity, and semi-supervised k-median/means, we obtain the first constant factor approximation algorithms to the best of our knowledge. 5) Since our algorithms are based on a simple sampling based approach, we also obtain constant-pass log-space streaming algorithms for most of the above-mentioned problems.
BibTeX
@inproceedings{goyal2020fpt,
  author = {Dishant Goyal and Ragesh Jaiswal and Amit Kumar},
  title = {{FPT Approximation for Constrained Metric k-Median/Means}},
  booktitle = {IPEC},
  year = {2020},
  url = {https://openreview.net/forum?id=cOY6V3zDYO},
}
Figure