Clustering under Constraints: Efficient Parameterized Approximation Schemes
Sujoy Bhore, Ameet Gadekar, Tanmay Inamdar · 2025
Read Clustering under Constraints: Efficient Parameterized Approximation Schemes by Sujoy Bhore, Ameet Gadekar, Tanmay Inamdar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-06980.txt.
Introduction
Sujoy Bhore, Ameet Gadekar, and Tanmay Inamdar give fast approximation schemes for clustering with side constraints, in a 2025 theoretical computer science paper. Clustering points into k groups gets harder when rules are added, such as capacity limits, fairness, or backup centers. Their unified framework works on metric spaces with bounded scatter dimension, a family that includes Euclidean space, planar maps, and many graph metrics.
Earlier methods in this setting only handled objectives where each point joins its nearest center. The new schemes cover the constrained variants in full, giving the first such guarantees for capacitated and fair median and means problems beyond Euclidean space. They also speed up the plain versions. The result answers an open question posed by the scatter dimension framework's founders.
Catalog record
| CREATOR | Sujoy Bhore, Ameet Gadekar, Tanmay Inamdar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-06980
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Clustering under Constraints: Efficient Parameterized Approximation Schemes Sujoy Bhore, Ameet Gadekar, Tanmay Inamdar Abstract Constrained k k -clustering is a general framework for clustering that captures a wide range of structural and assignment constraints, including capacities, fairness, outliers, and matroid restrictions. Despite its broad applicability, efficient parameterized approximation schemes (EPASes) for these problems were previously known only in continuous Euclidean spaces or for formulations restricted to Voronoi assignments, where each point is assigned to its nearest center. Moreover, it is known that EPASes cannot exist in general metric spaces. We present a unified framework that yields EPASes for constrained ( k , z ) (k,z) -clustering in metric spaces of bounded (algorithmic) scatter dimension, a notion introduced by Abbasi et al. (FOCS 2023). They showed that several well known metric families, including continuous Euclidean spaces, bounded doubling spaces, planar metrics, and bounded treewidth metrics, have bounded scatter dimension. Subsequently, Bourneuf and Pilipczuk (SODA 2025) proved that this also holds for metrics induced by graphs from any fixed proper minor closed class. Our result, in particular, addresses a major open question of Abbasi et al., whose approach to k k -clustering in such metrics was inherently limited to Voronoi-based objectives, where each point is connected only to its nearest chosen center. As a consequence of our framework, we obtain EPASes for several constrained clustering problems, including capacitated and matroid ( k , z ) (k,z) -clustering, fault tolerant and fair ( k , z ) (k,z) -clustering, as well as for metrics of bounded highway dimension. In particular, our results on capacitated and fair k k -Median and k k -Means provide the first EPASes for these problems across broad families of structured metrics. Previously, such results were known only in continuous Euclidean spaces, due to the works of Cohen-Addad and Li (ICALP 2019) and Bandyapadhyay, Fomin, and Simonov (ICALP 2021; JCSS 2024), respectively. Along the way, we also obtain faster EPASes for uncapacitated k k -Median and k k -Means, improving upon the running time of the algorithm by Abbasi et al. (FOCS 2023). 1 Introduction Clustering and facility location problems form a central theme in modern algorithmic theory. Given a set of points with pairwise distances, the goal is to choose a small number of representative centers and assign points to them in a way that minimizes an aggregate measure of distance. This paradigm captures a wide range of applications in data analysis, machine learning, and operations research. Traditionally, clustering is viewed as partitioning the dataset, where each point belongs to a single cluster represented by its nearest center. A broader and more flexible perspective, however, treats these problems as assignment optimization: each point can distribute its weight among multiple facilities under certain structural or resource constraints (see, e.g., [ 52 , 16 , 44 , 6 ] ). Among the best known formulations of clustering are the classical k -Median and k -Means problems, which have been studied intensively across theoretical computer science, machine learning, and optimization for several decades (see, e.g., [ 41 , 36 , 4 , 20 , 47 ] ). These models seek k centers that minimize the total (or squared) distance from each point to its assigned center. Over time, several more realistic and constrained variants have been explored. Among these, the Capacitated k - Median and k - Means problems stand out, where each center can serve only a limited number of points or must satisfy additional combinatorial restrictions on the set of open centers. Such constrained variants naturally arise in network design, resource allocation, and facility planning, and are substantially harder from an algorithmic standpoint. Despite decades of work, Capacitated k -Median remains one of the central open problems in approximation algorithms: the best known approximation ratio in general metrics is O(\log k) , obtained via probabilistic embeddings of metrics into trees [ 2 ] . Constant factor approximations are known only when either the capacities [ 49 , 48 ] or the number of clusters [ 28 , 14 ] are allowed to be violated by a (1+\varepsilon) factor. On the hardness side, the strongest lower bound known, (1+\frac{2}{e}-\varepsilon) under Gap-ETH, is inherited directly from the uncapacitated version. These gaps between upper and lower bounds have motivated the search for improved approximations in structured metrics, often by allowing fixed parameter or quasi polynomial running time [ 23 , 9 ] . In recent years, the connection between the geometric structure of metrics and the design of parameterized approximation algorithms has become increasingly prominent. Cohen-Addad and Li [ 23 ] obtained a (3+\varepsilon) approximation for Capacitated k -Median in general metrics with running time fixed parameter tractable (FPT) in k and \varepsilon . Notably, for the uncapacitated case, the lower bound of (1+\frac{2}{e}) can be matched by an FPT algorithm [ 22 ] . A central question thus arises: for which families of metric spaces can one obtain better upper bounds for Capacitated k -Median or k Means? The only affirmative progress is known for Euclidean metrics, where Cohen-Addad and Li showed that (1+\varepsilon) approximation algorithms exist for both problems with running time f(\varepsilon,k)\,n^{O(1)} [ 23 ] (see also [ 9 ] ). 1 1 1 In this context, a recent work of Huang et al. [ 38 ] on coresets for constrained clustering is also relevant; we discuss its implications in Section 4.3 . As mentioned before, stronger upper bounds are known for the uncapacitated versions of the problem. Indeed, Cohen-Addad et al. [ 22 ] obtained tight (1+\frac{2}{e}+\varepsilon) and (1+\frac{8}{e}+\varepsilon) approximation factors for k -Median and k -Means, respectively, in general metric spaces, with running times fixed parameter tractable (FPT) in k and \varepsilon . However, an important question remains: can these lower bound barriers for uncapacitated k -Median and k -Means be broken for structured metric spaces? This question has driven a series of advances in Euclidean settings, where geometric structure enables substantially stronger approximation guarantees. Bădoiu, Har-Peled, and Indyk [ 4 ] showed that, for points in \mathbb{R}^{d} , a (1+\varepsilon) -approximate k -Median can be computed in expected time 2^{(k/\varepsilon)^{O(1)}}d^{O(1)}n\log^{O(k)}n . Har-Peled and Mazumdar [ 37 ] subsequently proved the existence of small coresets for both k -Median and k -Means in low dimensions, while Kumar, Sabharwal, and Sen [ 47 ] gave simple randomized algorithms achieving (1+\varepsilon) approximations with constant probability in O(2^{(k/\varepsilon)^{O(1)}}dn) time. A common theme among these works is the use of geometric sampling and coreset constructions that exploit Euclidean structure. Most of these algorithms address the continuous setting, where centers may be placed anywhere in \mathbb{R}^{d} , although the result of [ 47 ] also applies to the discrete k -Means problem. Over the past decade, coreset techniques have evolved into a general algorithmic framework for clustering across diverse metric spaces. Feldman et al. [ 32 ] constructed coresets for k -Means, PCA, and projective clustering whose sizes are independent of the dimension, and Sohler and Woodruff [ 53 ] extended these ideas to k -Median and subspace approximation. Braverman et al. [ 13 ] developed coresets for k -Median in excluded-minor metrics. After a long sequence of advances [ 31 , 5 , 39 , 13 ] , Cohen-Addad et al.