EL-Clustering: Combining Upper- and Lower-Bounded Clusterings for Equitable Load Constraints
Authors: Rajni Dabas
Neelima Gupta
Rudra Bhardwaj
Sapna Grover
Venue: Accepted by TMLR ()

Abstract: The application of an ordinary clustering algorithm may yield a clustering output where the number of points per cluster (cluster size) varies significantly. In settings where the centers correspond to facilities that provide a service, this can be highly undesirable as the cluster size is essentially the service load for a facility. While prior work has considered imposing either a lower bound on the cluster sizes or an upper bound, imposing both bounds simultaneously has seen limited work, especially for the $k$-median objective, despite its strong practical motivation. In this paper, we solve the \emph{equitable load} (\EL{}) clustering problem where we minimize the $k$-median objective subject to the cluster sizes not exceeding an upper bound or falling below a lower bound. We solve this problem using a modular approach. Specifically, given a clustering solution that satisfies the lower bound constraints and another that satisfies the upper bound constraints, we introduce a combination algorithm which essentially combines both solutions to produce one that satisfies both constraints simultaneously at the expense of a bounded degradation in the $k$-median objective and a slight violation of the upper bound. Our combination algorithm runs in $O(k^3+n)$ time, where $n$ is the number of points and is faster than standard $k$-median algorithms that satisfy either the lower or upper bound constraints. Interestingly, our results can be generalized to various other clustering objectives, including the $k$-means objective. We also do empirical evaluation for $k$-Median objective on benchmark datasets to show that both, the cost as well as the violation factor are significantly smaller in practice than the theoretical worst-case guarantees\footnote{https://github.com/0-rudra-0/el-clustering}.

Published in Transactions on Machine Learning Research (09/2025)
EL- EL-Clustering: Combining Upper- and Lower-Bounded Clus- terings for Equitable Load Constraints
Rajni Dabas"
miji. du.
Deportment of Computer Science, Northwestern University P.G.D.A.V. College, University of Delli
Neclima Guptal
nguptaaics.cm du ac ac.in
Department Computer Science, University of Delhi
Rudra Bhardwaj
rudramsc2/ @es. du. oc
Department of Computer Science, University of Delhi
Sapna Grover
sgrover
Department of Computer Science, University of Dellei Dyal Singh College, University of Delhi
Reviewed on OpenReview: https: // openreview. net/ formm? id= EkjDfnJ1gU
Abstract
The application of an ordinary clustering algorithm may yield a clustering output where the number points per cluster (cluster size) varies significantly. correspond to facilities that provide a service, this can be highly undesirable as the cluster size essentially the service load for a facility. While prior work has considered imposing either lower bound on the cluster sizes or an upper bound, imposing both bounds simul- tancously has seen limited work, especially for the k-median objective, despite its strong practical motivation. In this paper, solve the equitable load (EL) clustering problem where we minimize the k-median objective subject to the cluster sizes not excceding an upper bound or falling below a lower bound. We solve this problem using a modular ap- proach. Specifically, given a clustering solution that satisfies the lower bound constraints and another that satisfies the upper bound constraints, we introduce combination algorithm which essentially combines both solutions produce one that satisfies both constraints simultaneously at the expense of bounded degradation in the k-median objective and slight violation of the upper bound. Our combination algorithm runs in O(k3 + n) time, where is the number of points and is faster than standard k-median algorithms that satisfy either the lower or upper bound constraints. Interestingly, our results can be generalize lized to varions other clustering objectives, including the k-means objective. We also do empirical evaluation for k-Median objective on benchmark datasets to show that both, the cost as well as the violation factor are significantly smaller in practice than the theoretical worst-case guarantees.
settings where the conters
1 Introduction
Decision-making using algorithms powered by machine learning has become ubiquitous. Routinely, algo- rithms are used in consequential applications such as loan approval (Sheikh et al. (2020): Kadam et al.
(2021)), recidivism prodiction (Travaini et al. (2022): ; Kovalchuk et al. (2023)) ) and kidney exchange (Ash-
lagi & Roth (2021): : McElfresh al. (2020)). This has naturally brought greater attention to the broader
"This work done when the auhtor research scholar Department of Computer Science, University of Delhi 1 *Corresponding author.

---

Published in Transactions on Machine Learning Research (09/2025)
impact of these deployed algorithms and their vulnerability to noise and adversarial attacks, well as their societal consequences in terms of fairness and privacy. These additional considerations imply that there is a real need to solve non-standard variants of many problems to overcome these possible harmful consequences.
Variants of the standard clustering problem that take such considerations into account have received signifi- cant attention from the research community; this is unsurprising since clustering is a fundamental problem in unsupervised learning and classical problem in operations research. Examples of such works include Jones ct
al.
2021
|: Gupta et al. (2100); Kaplan & Stemmer (2018), who show algorithms for solving the k-median
and k- K-means problems that preserve the privacy of individuals using differential privacy. Further, Chhabra (020) and Cinà et al. (2022) study the performance of clustering algorithms when the datasct is af- fected by adversarial corruptions. Moreover, fairness considerations in clustering have received even greater attention comparatively (Chierichetti et al. (2017); Bercea et al. (2019); Bera et al. (2019): Kleindessner
ct al.
ct al.
(0199); Ahmadi et al. (2022); Chen et al. (2019): Li et al. (2021): Chakrabarti et al. (0022) Awasthi
ct al.
2022 The fair clustering literature has introduced a number of well-motivated fairness notions. At
least seven different. fairness notions have been introduced so far in clustering.
Despite the significant attention that has resulted in many variants of the classical clustering problem, we identify simple notion that has not received much attention from the community, even though it is well- motivated and has clear societal consequences. Specifically, from the operations research point of view, the selected centers in a clustering could represent facilities such as schools, with the cluster associated with each center (school) being the students assigned to that school. Naturally, a school requires a minimum number of students to maintain a good teaching quality at the same time the number of students should not exceed a certain threshold as the school's 's resources might be over-consumed leading to degradation in the teaching quality. One can also find a similar motivation if the schools were instead service centers providing services to clients instead of students. Each service center would want a minimum number of clients to bring in revenue; at the same time, the number of clients should not exceed threshold, as that would lead to issues such as higher waiting time and lower service quality. At a more precise level, this notion, which we call equilable service load (EL), simply stales that the size of each cluster (number of points in the cluster) should be both lower and upper bounded by some pre-set values simultaneously. This EL notion can also be motivated in machine learning applications such as market sogmentation. Specifically, since points in the same cluster would receive the same ads, might want to have level of equity between the different ads (centers) so that none receive too little revenue or dominate the market.
Though clustering under EL constraints has not received much attention, this notion is not entirely new. Specifically, the literature has considered variants of the standard clustering problem where lower and upper bounds on the cluster sizes have to be satisfied simultaneously (Frigsstad et al. (2016); Gupta et al. (2021): Ding et al. (2017): Rösner & Schmidt (2018)). However, the k-median variant of this problem (with lower and upper bounds) remains unsolved. Only heuristics have been introduced for the stringent case where the lower and upper bounds coincide (i.e., set to the same value); see de Maeyer et al. (2023) and citations within. Forcing the upper and lower bounds to be exactly equal is not practical since in most settings a small difference would be tolerated even if an exact equality was desired.
In this paper, we solve the m-median problem under EL constraints. Unlike the prior work, we follow a modular approach. Specifically, using a solution where the cluster sizes are all lower bounded and another where the cluster sizes are upper bounded, we introduce post-processing algorithm that combines the two to give a new solution that satisfies the EL constraints. Our combination algorithm runs in O +n) time, where is the number of points, and as such does not present a heavy computational burden. In fact, in comparison to existing algorithms for the k-median problem subject to either lower or upper bound constraint on the cluster size, our combination algorithm does not present the computational bottleneck in the algorithmic pipeline. Interestingly, although our main target is the k-median problem, we show how we can use our combination algorithm to solve other clustering variants under the EL constraints, including k-means clustering.
1 Soc the references therein for more. 2It. well-known and documented that interaction between students can improve the educational and social outcomes (ooller 200T);; Hurst et al. (2013)) but this would not be possible with very small student body.
2

---

Published in Transactions on Machine Learning Research (09/2025)
2 give notation along with the formal statement of the EL problem and some background on relevant prior work. In Section B we state our main theoretical results. In Section 4 we give an overview of additional related work to our problem. In Section S we give a high-level discussion of our main algorithmic techniques. In Section G we present our algorithm for EL Clustering for the k-median objective along with detailed technical prools that establish the guarantees of the algorithm. This followed by conclusion and a discussion of future work in Section 7 In addition, Appendix A discusses improvements to some of the theoretical guarantees when the gap between the lower and upper bounds is sufficiently large. Appendix B presents the algorithmic modifications required for other variants of the problem, while Appendix C contains the experimental setup and empirical evaluation.
Organization of the Paper. In Section
2 Notation, Problem Statement, and Background
In our problem, we are given a set of locations P in a metric space with metric c: P P - R2o, a subset C S P of n many points to be clustered. Further, we are given a set of (potential) center F C P and a positive integer k. Following the standard terminology in clustering and facility location, we will also refer the given points C clients and the centers F as facilities. As in standard k-median clustering, our objective is to find set of facilities F' F of at most & facilities (i.e., |F'| S k; note that this is called the cardinality constraint) and an assignment function C F' which assigns clients to the selected facilities so as to minimize the sum of distances between the clients and their assigned facilitics. More formally, we want to obtain a solution S = (F', .) that minimizes the objective function Cost(S) = ΣjEc e(j. a()).. Furthermore, in EL Clustering we are additionally given two parameters L and U where L is a lower bound on the cluster size and U the upper bound. follows that in a valid EL Clustering, the size any cluster is constrained lie in the range [L. U]. More precisely, denoting the set of points assigned to a center i F by o (i), it follows that L S -a- U. From the above description, the formal and concise definition of the EL Clustering problem is follows:
EL Clustering
Input: Instance I= F Optimization: min Exec c(j, a(j)) subject
Fl,
subset F F of size at most k,
assignment - F' such that for each facility i F L. (o) SU
We use three standard notions from the literature on approximation algorithms:
1. Approximation Factor. An algorithm is said to have an a-approzimation factor if, for every instance, the cost of the solution produces is at most a times the cost an optimal solution.
2. Violation Factor. A solution said to violate the upper bound constraint by factor 2 if the solution exceeds the constraint by at most a multiplicative factor of B. For example, in EL clustering, violation factor 3 means that no cluster has more than 3U clients.
3. Bi-criteria Approximation. A solution is an (a, cost at most a times optimal and violates upper bound constraint by at most a factor of 13
approzimation if it returns solution of
We next define two K-MEDIAN problems satisfying partial EL constraints (dropping one of the two, lower or upper bound constraints) whose solutions will be combined to obtain a solution for EL Clustering. In UPPER BOUNDED k-MEDIAN (UKM), we drop the lower bounds (which is equivalent to setting L. = 0), whereas in LOWER BOUNDED k-MEDIAN (LAM), we drop the upper bounds (by setting U n). Both of these problems have been extensively studied in the theoretical computer science literalure. Though interesting, upper bound constraints are notoriously hard to handle in problems like k-median. For example, finding constant factor approximation for UAM is one of the famous and long-standing open questions in the literature of
Note that it common in the classical k-median clustering select. the centers from the same set of points to clustered, this can captured formulation by simply setting setting F F=
3

---

Published in Transactions on Machine Learning Research (09/2025)
approximation algorithms. On the other hand, some heuristics do not provide any approximation ratio guarantees (i.e., a bound on the cost of the solution compared to the cost of the optimal solution). On the positive side, there are several papers that solve the problem by giving bi-criteria approximations that have an approximation ratio for the chustering objective, but also violate either the upper bounds or the cardinality constraint by a small multiplicative factor (Byrka et al. (015 2016;; Charikar et al. (1999):
Demirci & Li (2016); Korupolu et al. (2000); Li (2014 2015 (0166). For the L&M problem, both constant
lactor approximations and heuristics have been obtained (Arutyunova & Schmidt (2021 Guo al. (2020):
Han et al. 2020b
3 Our Results
In this paper, we study EL Clustering to obtain Theorem 3.1
Theorem 3.1. Given a solution Sy for UPPER BOUNDED R-MEDIAN (UkM) with an upper bound violation of factor 3 and solution St, for LOwER BOUNDED K-MEDIAN (LkM). .. If the clustering costs of the solutions are (Sp) and Cost(Sr), respectively. Then a solution of cost at most (7Cost(Su) + 2Cost(Sr)) can be obtoined for EL Clustering at a violation of the upper bound by a factor of (B + 1) and in run-time of O(k3 + n))
Note that the O + n) runtime stated above refers only to the combination slep that merges the given solutions Sy and Sz: it does not include the time required to compute Su and St, which depends on the algorithms used for UPPER BOUNDED i-MEDIAN and LOWER BOUNDED k-MEDIAN. The theorem also establishes bounds on the clustering cost and the violation in the upper bound constraints using any two given solutions, even if these solutions result. from heuristics. Tt. follows that if we obtain these solutions using approximation algorithms for UPPER BOUNDED K-MEDIAN and LOWER BOUNDED K-MEDIAN, then we can establish approximation ratio guarantees for EL solution as shown in the corollary below:
Corollary 3.2. Given an au approzimation for UPPER BOUNDED M-MEDIAN with 3 violation in the upper bounds and a1, approrimation for LOWER BOUNDED k-MEDIAN, Tay + 2az, approcimation can be obtoined for EL Clustering with a (3 + 1) violation in upper bounds in O(k3 +n) time.
Applying cxisting algorithms in Corollary 3.2 immediately yields concrete bounds: using the 16- approximation with 3-factor upper bound violation of Charikar et al. (1999) for UkM and the 387- approximation for LLM of Han et al. (2020a), we obtain an 880-approxnnation with 4-factor violation. Alternatively, with the ((1/=") "aap="=)pppoxiiaatiio of Byrka et al. (2016) for UAM and small & > O, the violation factor approaches 2. The constants here are driven by the underlying algorithms for U&M and LAM, and any future improvements these directly improve our guarantees.
Moreover, our combination approach works independently of the specific technique used in these algorithms; the result holds even if the imput solutions produced by heuristics without formal guarantees, in which case our algorithm preserves their practical performance. For instance, by applying the Fixed Parameter Tractable (FPT) approximation algorithms F for UkM and L&M by Goyal et al. (2020), the approximation factor for EL clustering can be reduced to (27+c) with a 2-factor violation in upper bounds, while maintaining an FPT runtime in k.
Furthermore, the computational overhead incurred by our algorithm in combining the solutions only O + +n) whereas all algorithms" for UkM and L&M require solving a linear programming problem and
hence takes at least wrre)) time (Vaidya 19899) Jiang et al. (2020); Cohen et al. (2021): van den Brand ()
Interestingly, our technique can be extended to other clustering variants, such as k-MEANS, k-CENTER, FACILITY LOCATION and KNAPSACK MEDIAN in the presence of EL constraints. Although we are able to extend the result to the k-Means problem, the constants associated with the cost of generating a means clustering with equitable load are relatively high in our paper. Improving these constants remains an
4 An algorithm FPT if its runtime upper bounded by O(f(k) n²) where is constant but f(k) be exponential in kt see Cygan et. 2015; for more details.
5 "Except Korupolu al. (2000) that uses local search but opens (5 + r)k facilities instead
4

---

Published in Transactions on Machine Learning Research (09/2025)
interesting open question for future work. We mainly focus k-median in the paper; modifications in the algorithm for other problems can be found in the supplementary material (Appendix B
In the supplementary material (Appendix A , we show an improvement in the upper bound violation for a particular scenario when the gap between the lower and the upper bounds is not too small, specifically when 2T S U. Note that this a reasonable scenario that likely to occur real applications. For this special case, we reduce the violation in the upper bounds to (B + e) at the expense of an increase of a factor of ((1cc) in the cost for a constant 0.
Finally, we complement our theoretical guarantees with an empirical evaluation (Section on benchmark datasets, showing that the cost as well as the violation factor are substantially better than the worst case guarantees in most of the cases. It is observed that the cost overhead is within 20% of the cost of maximum of the LkM and UAM solutions and it is typically within 10 10-11%, whereas the violation factor is within 1.54 in 80% of the cases.
4 Additional Related Work
As mentioned earlier, EL Clustering has not received much attention from the community. Heuristics are known for the problem when the lower and upper bounds coincide (Höppner & Klawonn (2008); Dinler & Tural (2016); de Maeyer et al. (2023); Lin et al. (2019); Ganganath et al. (2014); Chakraborty & Das 2019
Tang et al. (2019)) ). However, forcing the upper and lower bounds to be exactly equal is highly impractical
(2033) provide heuristics for k-means since in most settings only lower and upper bounds are desired. Lei el al.
clustering with EL constraints. Approximation algorithms have been obtained for clustering objectives other than the k-median and k-means. For example, Friggstad et al. (2016) gave an approximation algorithm for with EL constraints violating both the bounds by a constant factor with a trade-off in
Facility location o them whereas Gupta et al. (2021) gave an approximation algorithm violating the upper bounds by a factor of 5/2. For k-center with EL constraints, Ding al. (2017) and Rösner & Schmidt (2018) independently gave constant factor approximations. To the best of our knowledge, the k-median problem with EL constraints has not been studied before in the literature.
Some prior works in fair clustering bear some resemblance to our work. For example, in settings where the points in the dataset belong to different demographic groups, the works of Chierichetti et al. (2017); Bercea et al. (2019) Bera et al. (2019); Esmaaili et al. (2020); Ahmadian et al. (2019) have considered a fairness notion where cach cluster is constrained have close population-lovel proportions of each group. While this notion is similar
ours, there is considerable difference since the bounds are not imposed the cluster sizes as we do, but rather the proportions of the groups in each cluster. Further, another notion in fair clustering imposes lower and upper bounds not on the proportions of the demographie groups in each cluster but on the number of centers selected from each demographic group (Kleindessner et al. (2019h Jones et al.] (2020); Hotegni et al. (2023)). ), i.e., in a dataset that consists of 50% from a "blue" group and 50% from a "red" " group then we cluster with = 10, it may be desired to have at least 3 centers selected from each group and at most 7 centers from one group, thereby ensuring both measure of diversity and restricted dominance in the selected centers. However, this notion is also different from the EL notion. Interestingly, Dickerson et al. (2024) present modular approach to combine both demographic fairness notions mentioned above sinultaneously. Although the above-mentionel demographic notions are different from imposing lower and upper bounds on the cluster sizes, the objective of Dickerson et al. (2024) of combining two notions simultaneously is similar to our objective. Further, their modular approach of post-proccssing existing solutions is also similar to our approach, although at a high level, our constraints and techniques are very different.
In the facility location problem, instead of a hard bound k the number of facilities, every facility has a facility opening cost and the goal now is minimize the total cost of opening subset of facilities and serving the clients from these opened facilities.
We denote the demographic groups with colors as done in fair clustering papers. Concretely, these colors could denote attributes such as age, gender, or race.
5

---

Published in Transactions on Machine Learning Research (09/2023)
i open
702
9B 94
ge
91
1/2 open
ga
94
order: y1 82
M4
bag after v1. Va: 1+3
< residual bag + reserved 3 < (3 + IJU
= Toy examples for one star with L = 4, - and 3 = 1; the numbers in solid (grey) circle represents the reserved clients at star center i. Numbers in circles at the spokes represents unsettled unreserved clients. A bag of unsettled clients is accumulated while scanning spokes in decreasing distance from the center i. Whenever the bag first reaches I,, the current spoke opens (except for last spoke). At the end, the center opens for all the remaining clients at last spoke along with the reserved clients.
Figure 1:
5 High Level Idea of Our Algorithm
Our approach begins by decomposing the EL Clustering instance into two simpler subproblems: (1) A lower- bounded k-median instance It, obtained by dropping the upper bounds, and (ii) An upper-bounded k-median instance Iv, obtained by dropping the lower bounds. We solve (i) and (di) using any available algorithms (approximate or heuristic), obtaining solutions St and Sy respectively.
Before presenting the details of the combination algorithm, we introduce the following key terms that will be used throughout the algorithmic descriptions.
Star: subgraph formed by a facility (the star-center) in Sn and a set of facilities from the Su (its spokes) for which i is the closest facility among all facilities in the lower-bounded solution.
Open facility: A facility selected in the final EL Clustering solution to serve clients.
Closed facility: A facility not selected in the final EL Clustering solution.
We now describe our combination algorithm.
Grouping facilities into Stars: We group facilities into slars. For each facility opened the solution St, we form a star 8 consisting of (the star-center) and all facilities i' opened in the solution Sy whose closest Sz facility is i.
Processing stars: Opening and Closing Facilities within Star: Within each star S,, we consider its spokes in decreasing order of distance from i. We maintain a "bag" collecting unsettled clients from Sy assignments; when the bag size reaches the lower bound L, we open the current spoke facility (except for the last spoke) and assign all clients the bag to it. For all the clients accumulated at. the last spoke, we open To achieve claimed lower and upper bounds exactly enough (max(0, Jelients last spokel)), clients are reserved before processing the star and assigned to the facility when is opened. Refer Figure for a simple toy example.
The naive approach of processing stars in arbitrary order can lead to client conflicts, where clients intended for one star-center in S,. have already been assigned to spokes in another star. To avoid this, we build a dependency graph whose nodes are stars and whose edges represent shared clients between center of one star and the spokes of another star. We transform the built graph into an almost-DAC DAG (removing cycles except self-loops) via a careful reassignment step. Processing stars in topological order ensures premature client assignments.
Determine Processing Order:

---

Published in Transactions on Machine Learning Research (09/2023)
S
(occurence o)
Fu
of clients 1 8U
FL
no. of eeeientt 2
5:
(a)
(b)
= 4. Black and grey Figure 2: (a) Graph G1: Iz is an instance of L&M and by that of UkM. (b) Let L edges show the assignment of clients in St and Sy, respectively. Star S., is processed before star S, Clients j.j' assigned to in Sr. have already been assigned to facilities in 17 "f²) and hence are not available while processing S,.
6 Our Algorithm for EL Clustering
Let T == (,, be an instance of EL Clustering. We first create an instance T of L&M from by dropping the upper bounds and then an instance ly of UkM by dropping the lower bounds from I. Let S, = (r) and Sy (Fv.ov) be solutions It and Iy, respectively. Let denote the violation in upper bounds, if any, in Sy. In the next section, we combine solutions Sy and Sy obtain a solution S 01) to I with (B + 1) factor violation in upper bounds.
6.1 Combining solutions Sn and St to obtain S
To obtain a solution 5 = ()) to I, we will open some facilities in Fu.. We construct a directed graph G₁ on the set facilities in Fr, FF. For a facility E Fu, let m7()) denote the facility in Fr, nearest (assuming that the distances are distinct). Add an edge (i, m()) in the graph. Note that a facility may be open in both St. and Su, in that case E 1 (i). In order to avoid self loops, when i == 77)), we denote the occurrence of i in Fu by ie so that 77ic) i. Thus, obtain forest of trees where-in each tree is stur. Formally, we define star S; to be collection of nodes in (i) - with i E Fr as the slar-center and 17 1 S Fv. See Figure (a).
We process the stars to decide the set of facilities to open in FLUFu. Consider a star S, centered at facility i. Clearly, the total assignments on in Sr. satisfy the lower bound but may violate the upper bound arbitrarily. On the other hand, the total assignments on a facility i' E n (i) in Sy satisfy the upper bound (within B factor) but may violate the lower bound arbitrarily. We close some facilities in - by transferring their clients (in Sy) to other facilities in 17 (()) if possible (or to i, if required) and open those at which the lower bound is satisfied. We may also have to open i in the process. We make sure that upper bound is violated within the claimed bounds and the total number of facilities opened in S; is at most (y7 (i)]- The cardinality constraint is, hence, satisfied.
Suppose we consider the facilities (1) in the order of decreasing distance from Let the order be Vi, 12, W. We wish to collect the clients assigned to them, by Sy, in a bag looking for facility at which we would have collected at least L clients so that we open t, empty the bag by assigning all the clients in the bag to t and start the process again with the next facility in the order. The problem occurs when at the last facility (Ix), in the order, the bag has less than L clients. In this case, we would like to assign these clients to the star-center i making use of the fact that i was assigned at least L clients in S,.- The problem here is that the clients assigned to in Sp might have been assigned to the facilities in 1j "1()) for some star Sy processed carlier or to the facilities in 17 (i) itself. Figure (b) explains the situation. Thus, we neod to process the stars in a carefully chosen sequence so as to avoid this kind of dependency amongst them. That is, the stars should be processed in such way that if, at any point of time, we are processing star
7

---

Published in Transactions on Machine Learning Research (09/2025)
S, then the clients assigned to i in Sy are not assigned to facilities in 17 "=')))) in Sy for star Sy processed earlier. For this, we construct weighted directed (dependency) graph G2 (possibly with directed cycles) on stars and convert it into a directed acyelic graph (DAG) (except possibly for self-loops), before processing the stars. topological ordering in the graph, then gives us the order in which the stars must be processod. We will denote the graph by G2(aL; Tv) to show that is a function of the assignments Sz and Su-
The graph ou) has the stars { {S (t)] > 0} the vertices. Let X(i1, (() = -i EjeC: (o::o(i== n (12) and oz( = i ie., x()),12) i2) is the set of clients that are served by i in Sr. and by some facility at the spoke of the star centered at 22 in Sy. We include the directed edge ,S,,,S,)) from star St, to St, if (111,)2)) > O. Let :(S.;;;;;) = (1 i2)l denote the weight on the edge (Si, S:2). Refer to Algorithm [ and Figure (a) (c) for the construction of graph G2. Initially, (2) = 0 and w(S, Sig) = for all pairs of stars S and S (ir may be same as 12). If the resulting graph has no directed cycle except possibly the self-loops, we are done. The graph G2 an almost- DAG. A directed graph is called an Almost-DAG. if the only cycles in it are self loops. However, if there are non-trivial directod cycles the graph, we redefine the assignments in Sr. to obtain another solution Sr. (F1, ō1.) to break the cycles. The dependency graph for (8L, oU) will then be an almost- DAG.
Algorithm 1: Constructing Graph G2(0r,ov)
Input : Stars i
Output: Weighted Directed Graph G2( (V,E) (i) }, E+
V + {St: in
for j do
d' o') in to((), i2))
X(i,,12) + x(i, w(S,, S.,)) + (S,,,, +1 for each pair of slars S., Sig do if wWS,,, > 0 then E t EU (S S
8
Algorithm 2: Breaking Cycles: Constructing an almost- DAG G2(ōL,
Input : Graph G2(aL.
Output: Gz(ōL.00)
di) - (r Vj EC
while 3 directed cycle < St, Stg...,, (q > in G2 do
- w.S.,, Sig) // assume (1)) as the minimum weight edge in the cycle for r= to do
5
count +- 0, 8 t (r mod q) +1
6
for j E X' iz) do if count
7
then
8
dg( t is count +
9
X(ir,ia) +- Xir is) (i)
11
X((,, + X 1s) U Ut}
12
S(, + ( S, +
13
w(S S, + ( St,)
14
if W Sr,) then
15
E - E (St,, S, // Remove edge (Si,, from G2
16
EU S.,) // Add edge (S, in G2
Breaking the cycles: For graph Gz(ar, oU), let SC =< S S,y...,, S., > be a non-trivial directed cycle with q > Without loss of generality, let (S., St,) be the minimum weight edge in the cycle. We reassign any i nr(S,, Sig)) clients in Xiir mod +)+1) from i to iir mod 4)+1, increment the weight of the edge
8

---

Published in Transactions on Machine Learning Research (09/2025)
8/2
1
812
1
8/1
S
81p
S
K1
6
2
3
111
82
222
2
8/2
S
5
41
8
1/1
0.
00
13
A/
St
Su
Su
(a)
(b)
(c)
(d)
(e)
Figure 3: (a) Stars Sn, St and S (b) (2), {ii}: (i2, (/2 Js. (i3, (js.Jo3: (c) Its directed cycle ov); (d) Breaking a cycle: assign J1 to i2: Jt to 13 and js to i1, that is, 0z(5)) i2.
(1( = is and, (js) = da; (e) The sub-graph G2(ôL, ou) after breaking the cycle.
w(Ser mod +)++1 Sig mod (tt1) by x and, reduce the weight of the edge w(Si, Sty- med 94+1) by K. for r = 1..... q. Note that this adds new self-loops in the graph; however, no new non-trivial edge is added. Also, observe that | (i))
(i)) and hence ( (i) 2 L is maintained for all E Fr. after the reassignments. The weight of the edge (S., Sty) becomes zero and we remove it, thereby breaking the cycle. See Algorithm 2 and Figure (d) (e). Note that client gets reassigned at most once in all the cycles as during ro-assignment, it moves its contribution from a non-trivial edge to a self-loop and not to any other non-trivial edge. Next,
we bound the cost of solution Š₁ in the Lemma 6.1
Lemma 6.1. The cost, Cost(Sr), of solution Sr is bounded by Cost(St) + 2Cost(Su).
Proof. Let E C. The cost paid by j in solution Sr is (see Figure (a).): dii, oz(i) < clj, ovli)) + dfvv(f), o,.(1) I c(j, ov(()) + cj),(j), or(()) S c(j. + (c(or()), j) + tcj on(i))) = c(j, on(;)) 2elj, (i)),, where the second inequality holds since n()v(i)) = dz())). Summing over all j E C, we get the desired claim.
+
or = is on(
(I)
1' E 1 (i++1)
ou (1) = i'
c(i,, S clii (1)
i, (/in)
in (i1)
clo((i,)) clo () 00() oz00))
j
1' or(i)
i ".:.....
i,41 (/iz)
dli,2) S c(b, 22
i
ri) noou (f))
(a)
(b)
(c)
Figure 4: (a) c(j, oz()) s clj, oz(1))+2c() oi(i)): (b) Cost bound of Type- assignments; (c) Cost bound of Type-Il assignments.
Graph G2(ōL, ov) has the following properties:
1. G2(ōL, ou) is an aimost-DAG.
2. 107 (1) LViEFT.
9

---

Published in Transactions on Machine Learning Research (09/2025)
Now that have an almost-DAG on the stars, we process the stars in the sequence < S1g........ S.. defined by topological ordering of the vertices in G2(01, ov) (ignoring the self-loops). While processing the stars, we maintain partition of our clients into two sets, C, and C. of settled and unsettled clients respectively. We say that a client is settled it has been assigned to an open facility in S and unsettled otherwise. Initially C, = and C2 = C. As we process the stars, more and more clients get settled.
Algorithm 3: Process(S.)
Input :S; Fr,
reserved(1] 0, Bag t- 0
for E E) do
N2. Co
Arrange the facilities in 17 (i) in the sequence < V1.... y1 >> such that
clye, i) 2 cI i) A 1' = =1 1.../-1
if [N < then
reserved(i) t set of any L - 1. clients from (7) \ Ng for i' VEn E do
6
N₂ f- No reserved(i)
for 1 to
do
10
Bog t Bag Ny.
11
if [Bagl 2 then
12
Open facility yr for j E Bag do
13
14
Assign j to ye, C. c, C. + Cu Vi
15
Bag +
16 t 1ti
17 if |Bag U Nn, U Ureserved(i) > (3 + 1)U then
t 91 19 Open t
18
20 for j E Bag U Nu Ureserved(i) do Assign j to t, C. + C.uut (i) C. C. \ (53
Consider star S. Algorithm gives the processing of S; in detail. For i' E my let N₂. be the set of unsettled clients, assigned to in Sy. Consider the facilities in 77 (i) in decreasing order of distance from i, i.o., y/, U2. We make sure that at most one of y and i is opened. To meet the lower bound at when i is opened (and z closed if yt + i), we reserve max L LLLL--N,,, [N clients from 07. - (i) Nu: at i (line 6). Observe that the topological ordering of the stars ensures that | (i)l CCu n (i)l 2 L and hence (1) Nr 2 L I-,, We delete the reserved clients from N,, i' E E - (lines 7 8) before processing the facilities in n (t). In lines 9 - 15, as we process the facilities in 1))((),, we collect the unsettled clients assigned to the facilities in (i) by Str in a bag looking for facility at which we have collected at least L clients. We open t and empty the bag by assigning all the clients in the bag to t (called Type-I assignment)) and start the process again with the next facility in the order.
To make sure that we do not open more than [n)] facilities in S,, open only one of and y for the remaining (Bag U Ny, U reserved(i)) clients. This also ensures that do not open more than once. We prefer to open and give all the remaining clients to i because (as we will show later) the cost of assigning clients from Bag Ugg to is bounded whereas we do not know how to bound the cost of assigning clients in reserved(i) to y1- However, in case, it leads to more than acceptable violation in the capacity at i, we open I. and assign the remaining (Bog J N₂, U (rservedd()) clients to it. We show that reserved(1) is empty in the latter case. Algorithm summarizes our combination algorithm for constructing S from Sy and St.
6.2 Analysis
Recall that the assignments done in lines 9 15 are Type-I assignments. Let the assignment of clients
facility i when = i in lines 20 21 be called as Type-1l II assignments and those to facility y when & = y be
10

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm 4: Constructing S₁
Input : << Sp = FL,OL 2, St Fu.0u >
Output: S₁
Construct graph G1 =1=<FFUFFF
where E ((1, : e Fu).
Construct graph G2(a1,
Construct an almost-Dak DAG G2(ōL, from G2(0L, ov) using Algorithm
Obtain topological ordering < Si, S₁, > of stars in the almost- Mimost-DAGG G2(ōL,
for r = 1 to do
Process S,, using Algorithm
called as Type-III assignments. To prove our main theorem, we need show that in the obtained solution St, the lower bounds are respected, the upper bounds are violated by factor of at most (B + 1), the cost of the solution is bounded and the running time is O(k3 n). We first prove that the lower bounds are respected at the opened facilities in Lemina 6.2
Lemma 6.2. Number of clients assigned to an open facilily in F is al least L.
Proof. We will bound the lower bounds for all three type of assignments separately.
1. Observe that the facilities opened by Algorithm in line 12 (Type-1 assignment) satisfy the lower bounds by design of the algorithm.
In Type-Il assignments, the star-center i satisfies the lower bound (if opened at line 19) as |Bag U Ng. Ureserved(i) 2 where the inequality follows because |reserved(i)] = (0, I. IN }
In Type-III assignments, facility yt (if opened at line 19) also satisfics the lower bound as Bag U Ny Ureserved(i) > (8+ IJU 2 2L because U L and 3 2 1.
We next, show that the upper bounds are violated by factor of at most (8 + 1) at the opened facilities in Lemma 6.3
Lemma 6.3. Number of clients assigned to an open facility in F is no more than (8 + 1)U.
Proof. We will bound the violations in the upper bounds for three type of assignments separately.
Consider the facilitics in 17 1()). These facilities receive clients only in Type- assignments (lines
14- Note that for l' = 2, -....,--11 1-,,,,1, we have Bagl L just before line 10 and hence |Bagl L+ (just after line 10) < (1 B)U because L < U. For l' 1, |agg 0 just before line 10 and hence
[Bagl= s BU (just after line 10).
2. For Type-II assignments, the bound holds trivially because the star-center reccives clients only when Bagl + N + |reserved(i] < (B + +)U.
3. The maximum number clients received by facility y1 in Type-III assignments is, |Bagl + |N + (reserved(1) = |Bagl + N + max - NN,, = [Bagl + max(L, N < L + JU < (8 + 1)U.
The next lemma (Lemma 6.4 bounds the cost of our solution (Sr) in terms of cost of solution Sy and St. Lemma 6.4. The cost of solution S₁ is bounded by TCost(Se) + 2Cos
Proof. Consider star Si-
11

---

Published in Transactions on Machine Learning Research (09/2025)
1. Type-I assignments: Let j C be assigned to facility i2 n (n'(() in our solution and to i 17" (n) in Sy i.e., i (i) and i2 or(;). The cost paid by j is (see Figure (b)):
c(i2. 1) s c(i j) + dii, i) + té, i2)
S <c(in. +)+ 2c(i1, i)
+
S sii + 2e(ii, on(j))
(as m7(1) =
3o(in, j) + 2o(i, (i)
(by triangle inequality)
20(j, oz(i)) 7c(j, ou (1))
(by Lemma 6.1
2. Type- II assignments: Let j reserved(1) be assigned to Also, let j E No i' (1) be such that i' = (i). Then, the cost (see Figure (c)) is:
c(i, j) c(or(i), +)+ i)
= i) n(v((i))
((o,)),, 6z(1))
S sclov()), +)+ d(v((),, j) clj. oz())
2c(i, ov(j)) + c(i, oz(i))
4c(j, ov(i)) + ccj oz(i))
where the sccond and third equality follow because 0z(5) =i- n((o(())) and the last incquality Tollows by Lemia 6.1
3. Type-IIII assignments: Note that |Bag U Ny U Ureserve(()) (B 1)U = |reserved(i) 0, for otherwise N, (rssrvved()) = L and thus |Bag U N, Ureserved(i) < L + L < 2U because 1, < U. Hence, the cost of assigning [ag U N clients to yn is bounded in the same manner as the cost of Type-I assignments.
By summing the cost over all the assignments of Type-I, Type-II and Type-III, we get, Cost(Si) TCost(Sr)+ + 2Soos((Sr)
We finally show bounds on the running time of our algorithm in the following lemma. Lemma 6.5. Running time of our combination algorithm (Algorithm is O(K* + n.)
Proof. Constructing G1 takes O(k2) time and the graph G2 can be constructed in time O(n + kP); for each client j. one can determine the edge (2),2) to which j contributes in constant time. G2 can be converted into almost-DAC in O(K3 +n) time using DFS and Algorithm 2: computing minimum weight edges takes at most ( time over the entire algorithm and every client ro-assigned Algorithm 3 when executed on all stars is no more than O(n + k log k); note that in this case also, client is re-assigned at most once; & llog k comes from sorting in step 4. Thus, having obtained solutions to L&M and UkM, combining the two solutions take O(k3 + n) time.
most once. The time taken by
Since any solution to 1 is feasible for I and Tv we have Cost(S)) < Cost(S)) and Cost(Sv) S Cost(S)). Therefore, the proof of Theorem 3.1 follows from Lemmas 6.2
6.3
6.4
and, 6.5 Furthermore, we have
(Or) < COs((O) and Cost(Ov) < Cost(O), where O, Oz and OU denote optimal solution to I, It and Iv, respectively. Therefore, the proof of Corollary 3.2 follows from Theorem 3.1 and by using approximation algorithms such as Byrka al. (2016) for UkM obtain Sy and Han et al. (2020a for LkM to obtain St.
7 Conclusion and Future Work
In this paper, we presented a modular approach for solving the EL Clustering problem by combining a solution of the k-median problem where the cluster sizes are lower bounded with another where the cluster sizes are upper bounded. Our solution introduces bounded degradation over the costs of the given solutions.
12

---

Published in Transactions on Machine Learning Research (09/2025)
Further, given solution to the upper bounded instance where the upper bounds are violated by 8 our solution only incurs a bounded additional violation leading to at most a B + violation. An advantage of our method is that it gains from any improvements in the upper bounded and lower bounded solutions. Specifically, solutions for the upper and lower bounded instances with better approximation ratios enable us to obtain solutions with a better approximation ratio for EL. A similar note follows for solutions with smaller 3 violations in the upper bound. Interestingly, we note that Lemma 6.2 and Lemma 6.3 and hence our results hold for more general scenario where the lower and upper bounds are not necessarily the same across the facilities, the only restriction is that m L3 I minge Ug. Furthermore, we discussed how our algorithm can be applied to other clustering variants including k-means clustering. Moreover, for the special case when the gap between the lower and upper bounds is large enough (specifically, 2L; S U, F) the violation in the upper bound can be reduced to 3 + for a given e 0.
One direction for future work would be to get rid of the plus 1 violation in the upper bounds. Another interesting direction is to extend the results general lower and upper bounds. We acknowledge that the constants associated with the cost of generating a k-means clustering with equitable load are rather high in our paper. Improving these constants is another useful direction for future work.
References
Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, and Surabhi Jain. A 3-approximation algorithm for the facility location problem with uniform capacities. Journal of Math. Prog., 141(1-2):527-544) 2013.
Gagan Aggarwal, Rina Panigrahy, Tomás Feder, Adam Meyerson, and Samir Khuller. Achieving anonymity via clustering. In Proceedings of the 25th ACM STCMOD-SICACTT-SCARR Symposium on Principles of Dalabase Systems (PODS), pp. 153 162, 2006. doi: 10. 10.145/1144351.114237
Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Matthäus Kleindessner, Jamie Morgenstern, Pat- tara Sukprasert, and Ali Vakilian. Individual preference stability for clustering. arXin preprint wwXiv:2207.03600 2022.
Sara Ahmadian and Chaitanya Swamy. Improved approximation guarantees for lower-boudeed facility loca- tion. In Approsimation and Online Algoritlems, pp. 257-277777 2013.
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over- representation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discov- ery & Data Mining, pp. 267 275, 2019.
M. Almanza, A. Epasto, A. Panconesi, and G. Re. k-Clustering with Fair Outliers. In Proceedings of the 15th ACM International Conference on Web Search and Dala Minnng (WSDM), pp. 5-15, 2022.
Anna Arutyunova. and Melanie Schmidt,. Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means. In STACS 2021, pp. 7:1-7:17, 2021.
Itai Ashlagi and Alvin E Roth. Kidney exchange: An operations perspective. Management Science, 67()): 5455 5478, 2021.
Pranjal Awasthi, Brian Brubach, Deeparnab Chakrabarty, John P
Dickerson, Seyed A. Esmacili, Matthäus Kleindessner, Marina Knittel, Jamie Morgenstern, Samira Samadi, Aravind Srinivasan, and Leonidas Tsepenekas. Fairness in clustering. 2022. URL http::://www.fiircllteeeee
Suman Kalyan Bera, Decparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alcch--Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, pp. 4955-4966 2019. URL http://prroeeingg..rrr..p.pp 22112000022700444447723333a22232 Abstttcccc.caatttt.........aa... html
13

---

Published in Transactions on Machine Learning Research (09/2025)
Ioana Oriana Bercea, Martin Groß; Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Dimitris Achlioptas and Tás- zóó A. Végh (eds.), Approzimation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/ APPROX/RANDOM /RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambbridge, MA, USA, volume 145 of LIPles, pp. 18:1-18:22 Schloss Dagstubl Leibnniz-Zentrum für URL /ttttttt/////t org/10. 42300/
Informatik, 2019. doi: 2019.18
TTA.......APOO-PAAAAAAAA LIPIcs APPROX-RANDOH 2019.
Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spocrhase. Bi-factor approximation algo- rithms for hard capacitated k-median problems. In SODA, 2015, pp. 722 736, 2015.
Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with (1 + e) capacity violation. In IPCO, pp. 262 224,274,22 2016.
Darshan Chakrabarti, John P Dickerson, Seyed A Esmaeili, Aravind Srinivasan, and Leonidas Tsepenekas. A new notion of individually fair clustering: a-equitable k-center. In International conference artificial intelligence and statistics, pp. 6387 6408. PMLR, 2022.
Debjani Chakraborty and Suman Das. Modified fuzzy o-mean for custom-sized clusters. Sädhanā, 44(8):182, 2019.
Moses Charikar, Sudipto Guha, Eva Tardos, and David B. Shmoys. A constant-factor approximation algo- rithm for the k-median problem (extended abstract). In STOC, 1999, pp. 1 10, 1999.
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In Interna- tional conference on machine learning, pp. 1032 1041. PMLR, 2019.
Anshuman Chhabra, Abhishek Roy, and Prasant Mohapatra. Suspicion- frree adversarial attacks on clustering algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3625 3632, 2020.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Sys- lems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5029 5037, 2017. URL
97stabbcceccc8dddee1111222 2at.2244aa-bbttaa....mm Abstract.htmm
Antonio Emanuele Cinå, Alessandro Torcinovich, and Marcello Pelillo. black box adversarial attack for poisoning clustering. Pattern Recognition, 122:108306, 2022.
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipezuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2013.
Rieke de Maeyer, Sami Sieranoja, and Pasi Fränti. Balanced k-means revisited. 2023.
H. Gökalp Demirci and Shi Li. Constant approximation for capacitated k-median with (1 + c) capacity violation. In ICALP, pp. 73:1 73:14, 2016.
John Dickerson, Scyed Esmacili, Jamic Н Morgenstern, and Claire Jic Zhang. Doubly constrained fair clustering, Advances in Neural Information Processing Systems, 36, 2024.
Hu Ding, Lunjia Hu, Lingxiao Huang, and Jian Li. Capacitated center problems with two-sided bounds and outliers. In WADS, pp. 225-336,74 2017.
Derya Dinler and Mustafa Kemal Tural. A survey of constrained clustering. In Unsupervised learning algorithms, pp. 207 235. Springer, 2016.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Dheeru Dua and Casey Graff. Uci machine learning repository. htttp://archive.1o. wwt.suciieeuuuuu 2017.
Seyed Esmacili, Brian Brubach, Leonidas Tsepenckas, and John Dickerson. Probabilistic fair clustering.
Advances in Neural Information Processing Systems, 33: $3:12743- 12743-127755, 2020.
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding. In SWAT, volume 53, pp. 1:1-1:14, 2016.
Nuwan Ganganath,
Cheng, and K Tse Chi. Data clustering with cluster size constraints using a modified k-means algorithm. In 2014 International Conference on Cyber- Enaee-E Distributed Computing and Knowledge Discovery, pp. 158 161. IEEE, 2014.
Dishant Goyal, Ragesh Jaiswal, and Amit Kumar. FPT approximation for constrainod metric median/mmanss CoRR, abs/2007.11773, 2020. URL
Sapna Grover, Neelima Gupla, Samir Khuller, and Aditya Pancholi. Constani factor approximalion algo- rithm for uniform hard capacitated knapsack median problem. In FSTTCS, pp. 23:1-23:22, 2018.
Yutian Guo, Junyu Huang, and Zhen Zhang. A constant factor approximation for bownrebounded k-median. In TAMC, pp. 119-131, 2020.
Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, and Kunal Talwar. Differentially private combinatorial optimization. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algoritlems, pp. 1106 1125. SIAM, 2010.
Neelima Gupla, Sapna Grover, and Rajni Dabas. Respecting lower bounds in uniform lower and upper bounded facility location problem. In COCOON, pp. 463-475, 2021.
Lu Han, Chunlin Hao, Chenchen Wu, and Zhenning Zhang. Approximation algorithms for the lower-bounded knapsack median problem. In AATM, volume 12290, pp. 130, 2020a.
Lu Han, Chunlin Hao, Chenchen Wi, and Zhenning Zhang. Approximation algorithms for the lower-bounded k-median and its generalizations. In COCOON, pp. 627 639, 2020b.
Frank Höppner and Frank Klawonn. Clustering with size constraints. In Lakhmi C. Jain, Mika Sato- llie, Maria Virvou, George A. Tsihrintzis, Valentina Emilia Balas, and Canicious Abeynayake (eds.), Computational Intelligence Paradigms, Innovative Applications, volume 137 of Studies in Computational Intelligence, pp. 167-180. Springer, 2008.
Sedjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algorithms for fair range clustering. In International Conference on Machine Learning, pp. 13270 13284. PMLR, 2023.
Beth Hurst, Randall R Wallace, and Sarah B Nixon. The impact of social interaction on student learning. Reading horizons, 2013.
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang, Faster dynamic matrix inverse for faster lps. arXiv preprint arXim:2004.074/00 2020.
Matthew Jones, Huy Nguyen, and Thy Nguyen. Fair k-centers via maximum matching. In International conference on machine learning, pp. 4940-499 PMIRR 2020.
Matthew Jones, Huy L. Nguyen, and Thy D Nguyen. Differentially private clustering via maximum coverage. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11555 11563, 2021.
Ashwini S Kadam, Shraddha R. Nikam, Ankita A Aher, Gayatri V Shelke, and Amar S Chandgude. Prediction for loan approval using machine learning algorithm. International Research Journal of Engineering and Technology (IRJET), 8(04), 2021.
Haim Kaplan and Uni Stemmer. Differentially private k-means with constant multiplicative error. arXiv preprint ar 18x: 08001, 2018.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Samir Khuller and Yoram J. Sussmann. The capacitated k-center problem. SIAM Journal Díscrete Mathemalics, pp. 418, 2000.
Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summa- rization. In International Conference on Machine Learning, pp. 3448 1148-3457. PMLR, 2019.
Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of local search heuristic for facility location problems. Journal of Alg., 37(1):146 188, 2000. ISSN 0196-6774.
Olha Kovalchuk, Mikolaj Karpinski, Serhiy Banakh, Mykhailo Kasianchuk, Ruslan Shevchuk, and Nataliya Zagorodna. Prediction machine learning models on propensity convicts to criminal recidivism. Information, 14(3):161, 2023.
Kai Lei, Sibo Wang, Weiwei Song, and Qilin Li. Size-constrained clustering using initial points selection method. In Knowledge Science, Engineering and Management: 6th International Conference, KSEM 2019, Dalian, China, August 10-12, 2013. Proceedings 6, pp. 195-203 Springer, 2013.
Bo Li, Lijun Li, Ankang Sun, Chenhao Wang, and Yinglan Wang. Approximate group fairness for clustering. In International conference on machine learning, pp. 6381 6391. PMLR, 2021.
Shanfei Li. An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem.
In APPROX/RANDOM, pp. 325-338, 2014.
Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. In SODA, pp. 696 707, 2015.
Shi Li. Approximating capacitated k-median with (1 c)k open facilities. In SODA, pp. 786-796, 2016.
Weibo Lin, Zhu Hc, and Mingyu Xiao. Balanced clustering: A uniform model and fast algorithm. In IJCAI, pp. 2987 2993, 2019.
Duncan McElfresh, Michael Curry, Tuomas Sandholm, and John Dickerson. Improving policy-constrained kidney exchange via pre-screening. Advances in Neural Information Processing Systems, 33:2674 26885, 2020.
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemar- keting. Decision Support Systems, 62:22-31. 31, 2014. ISSN 0167-9236. doi: 10.1016/j.dss..0000 2014.03.001. URL https: www.scceeeeee.ecccoo
Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. In ICALP, pp. 96:1 96:14, 2018.
Mohammad Ahmad Sheikh, Amit Kumar Goel, and Tapas Kumar. An approach for prediction of loan approval using machine learning algorithm. 2020 international conference on electronics and sustainable commumication systems (ICESC), pp. 490 494. IEEE, 2020.
Amy Soller. Supporting social interaction in intelligent collaborative learning system. International journal of artificial intelligence in education, 12:40-60 62, 2001.
Beata Strack, Jonathan P. Deshazo, Chris Gennings, Juan Luis Olmo Ortiz, Sebastian Ventura, Krzysztof J. Cios, and John N. Clore. Impact hbalc measurement on hospital readmission rates: Analysis of 70,000 clinical database patient records. MidMed Research Internationol, 2014:781670, 2014. doi: 10.1155/2014/
781670. URL httts:://oot /ttt:s:://oi..or/10... 111111111111//11111111111 Article ID 781670.
Wei Tang, Yang Yang, Lanling Zeng, and Yongzhao Zhan. Size constrained clustering with milp formulation. IEEE Access, 8:1587 1599, 2019.
Guido Vittorio Travaini, Federico Pacchioni, Silvia Bellumore, Marta Bosia, and Francesco De Micco. Ma- chine learning and criminal justice: systematic review of advanced methodology for recidivism risk prediction. International journal of ereironmendal research and public health, 19(17):10594, 2022.
16

---

Published in Transactions on Machine Learning Research (09/2025)
Pravin M Vaidya. Speeding-up up linear programming using fast matrix multiplication. In 30th annual sympo- sium on Joundalions of compuler science, pp. 332-333 337. TEEE Computer Society, 1989.
Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In Pro- ceedings of the Fourteenth Annual ACM-STAM Symposium Discrete Algorithms, pp- 259-278. STAM, 2020.
17

---

Published in Transactions on Machine Learning Research (09/2025)
A Reducing violation in upper bounds when 2L < U
Algorithm 5: Process(S.)
Input : : FL
reserved(1) t- 0, Bag t- 0
for E' (i) do
Ny. C. Nor (t')
Arrange the facilities in n- (t) in the sequence < V1.... y such that
dyy, i) 2 c1 i) A l' 1 ....l-1
if WN < L then
reserved(i) + set of any L - ye clients from 07.1() \ N for ET" (i) do
8
N2 f- No. reserved(i) Prec + neull, Preucount = 0
10
for = 1 to 1 do
Bag - Bag Ny 11
12
if [Bag 2 then
13
Open facility ye
14
Count +
15
for j E Bag do
16
if Count < BU then
17
Assign j to yo C, + C, Ci), C. + C, \ (z), Bog + Bag \ {ib, Count + +
18
else
19
Prev + yv 11 Prev denotes the last unopened facility in "7 -
20
Prevcount = Bagl
21
if |Bag UN, Ureserved(i) S (B + E)U then
22
Open i
for j E Bag U Ny, Ureserved(i) do Assign j to C. C, U (j), Cu + C. \
23
24
return
|Bag N,, Ureserved(i) s (8 + c)U then 28
if
27
Open y1
for j Bag Ny Ureserved()) do
29
Assign j to yr, C, + C,U (j), C. + Cu \ {5}
30
return
Open Prev and y // |reserved(i) = 0 when |Bag U Ny, Uresereed()) > (8 + c)U Count + 0
32
33
Bag= + Bag U Ny, Ureserved(i)
34 for jE Bag do
35
if Count L then
36
Assign j to Prec, C, C,, C. + C. (i), Bag Bag \ (i), Count else
38
Assign all remaining clients in Bag to yı and Break
In this section, assuming 2L < U, modify Algorithm to obtain Algorithm 5 that reduces the violation in upper bounds from (3 + 1) to (3 + E) for given
0. In particular, present the following results:
Theorem A.1. For 2L < U, given solution Su for UPPER BOUNDED K-MEDIAN (UkM) violating the upper bound by a factor of 3 and solution St for LOWER BOUNDED k-MEDIAN (LkM). If the clustering costs of the solutions are Cost(Sy) and Cost(Sr), respectively. Then, a solution of cost most (O(+) (SCs)))Cs))S + 2Cost(SL))) can obtained for EL Clustering that violates the upper bound by factor of (3 + c) for a fized 0.
18

---

Published in Transactions on Machine Learning Research (09/2025)
We do the following modifications to Algorithm 3 (i) on arriving at facility, say t, at which |Bagl 2 L, we open & and instead of emptying the bag, we assign only BU clients to t. Remaining clients are carried forward to the next facility in the order; (ii) we keep account of the last facility (in Prev), if any, that is not opened, and the number of clients in the bag at that instant (in Prevcoune) i..,, Prev is the facility ye for which Bagl < L immediately after line 14 (hence at line 23) and Pretcount = |Bagl at that time. We open Preu at the end, if required. This is done as follows: if [Bag U reserved(i) U N,,1 S (B + +U,, we are done (we open i(/m) and assign all clients it). Else, we open both Prev and y (at line 42) (note that Prev & y must exist in this case) and, distribute the clients in Bag U reserved(() U Ny among Prev and Ve, that they receive at least I clients. We will show that the service costs and the violation in upper bounds are bounded in this case.
Let the assignment of clients to facility Prev in line 47 be called as Type-IV assignments. The assignments in line 20, line 31 and lines 38 & 49 are Type-I, Type-Il and Type-III assignments respectively. Before we proceed to prove our claims, note that we open at most one of y and i: if is opened at line 29, we return at line 33 and thus yt is never opened in this case. As before, this ensures that is not opened more than once.
Clearly, lower bound is satisfied by Type-I and Type-IV assignments done in line 20 and 47 for the facilities opened in lines 16 and 42 respectively. Also, since |Bag U Ny, U (eserved 2 L,, lower bound is satisfied by Type-Il assignments done in line 31 for the facility opened in line 29. For Type- assignments done at line 38, |Bag U Nu U reserved((i] > (3 + e)U 2 (3 + L. Clearly, the upper bound is violated by a factor of at most (3 +c at the facilities opened in lines 16, 29, 36 and Prev in line 42. For the assignments done in line 49, we look at the status at line 42: [reserved(i)
L, hence Bag U reserved(() U Norl < L + L < U. Thus, |Bag U No1 U reserved((i] = |Bag U Nyi < L + BU. Also, Bag U Ny U Ureserved(i) > (8 + +cU > 2L. Thus, L < [Bgg U Ny U Urssrvee((i) - L < SU i.e., at line 49,
0, for otherwise |Ng, U reserved(t))
L< Bagl= < BU.
Costs of Type-I, Type-Il II and Type-Ill assignments are bounded in the same manner as in Section 6 To bound the service cost of Type-IV assignments (line 47), observe that |Bag Ureserved( yn |> (3 + +eU = [Bag]= > eU as |reserved(i) that Prev and Preucount do not change after exiting the for-loop at line 27. Thus, Prevccunt > cL after line 42 also and the cost of assigning at most L clients from Ny to Prev is bounded by (1/e) limes the cost of assigning eL clients from Up occurs before Prev in the order- Ny U Nrrev to yt. Hence, the total cost of TVpe-IV assignments is bounded by (1/e) total cost of Typee III assignments.
0 and 1N S BU; hence, Prevesunt 2 |Bag (at line 25) > el eL. Note
B Modifications for Other related Problems
B.1 k-Means with Equitable Load
The k-means problem with EL constraints is same as the k-median problem with EL constraints except that the goal now is to minimize the sum of the squared distances instead of minimizing the sum of distances from the assigned facilities. Further, the facilities to be selected in the k-means problem possibly belong to infinite space. Note that, in the k-means problem,
1. the distances are squared which may not satisfy triangle inequality but they satisfy a-relaxed triangle incquality, that is, c(x, y) S ac(x, 2) + ac(z, y) for a = 2 and,
2. can assume the set of facilities to be in finite space by losing 2a factor in the distances for a= 2.
We create an instance In of LOWER BOUNDED k-MEANS and Ty of UPPER BOUNDED k-MEANS instcad of LAM and UkM. Solution S7 is obtained by using the combination algorithm on Sy and St.- Note that, the violation in upper bounds remains the same, that is, for & violation in upper bounds in Sy, we get (B + 1) violation in upper bounds in Sy. We next bound the cost of the obtained solution Sy. With relaxed triangle inequality, Lemma 6.1 can be modified to bound the cost, Cos) of solution St by (S.) + (Su).
19

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma B.1. The cost of solution S₁ is bounded by 352Cost(So) + 192Cost(SL).
Proof. We will modily the proof Lemma 6.4 to accommodate relaxed triangle equality. Due to space con- straints, We will give details of Type-T assignments which have the dominating cost. Cost of Type-Ir II can be bounded by 30c(j, ot(i)) + 16c(1, (i) in similar manner. Cost of Type-Ill assignments is same Type-I assignments.
Type-I assignments: Consider a star S. Let j E C be assigned to a facility in E (n) and to is En (1) in Sy i.e., i, = =jr(j) and i2 or(i). The cost paid by j is: c(iz, j) I a c(i,, i) a di, 1) S
a a. ((2, +)+ (cli, i1) +clr, 1)) = a j) (a a² ee(i, i) sa² a² -du, j) + aa+a))d(in oz(1))
a² . c(t,, j) + (a² + a²) (c(1, j) + doj. or(i))) = (2a² + -(i. j) + (a² + a . oz(s))
16c(11, j) 12c(j. dz(G)) S 88c(j, ov(()) + +8c(j,, oz(i)), where the first, second, fourth incquality follow
by relaxed triangle inequality, third inequality follows as ni(1) = i, the last equality follows by setting value of to 2 and the last inequality follows by bound on Cost(SL))
We incur an additional multiplicative factor of 2a due to the assumption that the points lie in finite space. Multiplying by for a = 2, we get, (S) S 352Cos((Sv) ) + 192))st(St).
B.2 k-Center with Equitable Load
The k-CENTER problem with EL constraints is the same as the k-median with EL constraints except that the goal now is to minimize the maximum distance of a client from the assigned facility instead of minimizing the total distance. We create instance In and Iy of LOWER BOUNDED k-CENTER and UPPER BOUNDED K-CENTER respectively instead of L&M and UkM. Same bounds are obtained on the cost by taking the maximum of the cost of all the types of assignments. Bounds on violation in upper bounds remains the same.
B.3 k- k-Facility Location with Equitable Load
The k-FACILITY LOCATION with EL constraints a gencralization of the k-modian with EL constraints where for every facility i E F, we also have a facility opening cost ft. The objective now is identify F C F of size at most k and an assignment of clients to F to minimize the sum of the distances of the clients from their assigned facilities plus the facility opening costs of the selected facilities. We create instance Ir of LOWER BOUNDED &-FACILITY LOCATION by dropping the upper bounds and cardinality constraint. An instance Ty of UPPER BOUNDED k-FACILFTY LOCATION is created by dropping the lower bounds. We then follow the same procedure as described for k-median in Scction 6.1 to combinc the solutions of the two instances. Cost assigument bounded in the same manner. There is no loss in factor due to facility opening costs as we only open facilities in (FL Fu). The violation in the upper bounds remains the same.
B.4 Keepsack-Median with Equitable Load
KNAPSACK MEDIAN with EL constraints is another generalization of k-median with EL constraints where every facility i has weight fi and instcad of k, and we have a budget on the total weight. Therefore, the objective is to identify F' C F and an assignment a of clients to F' to minimize the sum of the distances of the clients from the assigned facility subject to the constraint Σ ft < B.
We first create an instance Iu of UPPER BOUNDED KNAPSACK MEDIAN by dropping the lower bounds and instance Jt. of LOwER BOUNDED KNAPSACK MEDIAN from I by dropping the upper bounds, reducing the set facilities to Fy and setting budget to the budget of Sy (note that this can be different from given budget B there is violation in budget in Sv, otherwise it B only). It can be shown that Cos)(Or,) S if a client j is assigned in the optimal solution O to I, to a facility i not in Fu. we assign it to facility i nearest to i, in Fv. The cost e(j, 8') clj, i) + c(i, 8) S c(j, i) + cii, i") S
(2 + (ost(Ss)))ost((((
20

---

Published in Transactions on Machine Learning Research (09/2025)
cti, 1) + c(j. i) + =(j, ;= 20(j, i) + e(j, (") where i" E Fu ov( 1" and the second inequality holds because i' is nearest to and not i"
We next use the same procedure as in Section 6.1 to combine solutions S₁, and Sy of instances L and lv respectively. Note that since FL S Fu, for E FL, Yi = = in the star S, This is important to make sure that the total facility opening cost in our solution is no more than that of Sy case we open i.
B.5
summary of approximation results using current best St and Su
Results for underlying problems
Our results
Previous results
Problem
(az)
(3.z))
(Bu- Bapproz)
LFL
U&M
M-Median
(82.6)
((1 + <), ()
((2 (2+1),0(1/22)
Nil
Ahmadian & Swamy 2013
Byrka et al. (0016)
LEC
UsC
k-Center
(2)
(1.6)
(2, 46)
Nil
Aggarwal et al. 2006
Khuller & Sussmann
2000
LFL
UFL
(0(1), 0(1)) *
Facility Location
(82.6)
(1,3)
(2, 186.2)
Friggstad ct al. 2016
Ahmadian & Swamy 2013
Aggarwal al.
(2013
LFL.
UkFL
k-Facility Location
(82.6)
((2 + +), +),0 ((1(z2))
((3 (3+0),0(1)2)
Ahmadiaa Swamy
2013
Grover et al.
2018
LKnM
UKnM
Knapsack Median"
(1608)
((2 | c), ((122))
((3 (3+c))0(112))
Nil
Han et al.
2020a
Grover et: al.
2018
Table 1: Our results. ag and ag indicate the approximation factor for the lower and upper bounded variant respectively of the problem under consideration. Also, Ou and Oappraz indicate the violation the upper bounds and the approximation factor respectively for the corresponding lower and upper bounded problem. 'Nil' represents that there is no result known for the problem. (*): the result violates the budget by a factor of (1 + e). (#): the result violates the lower bounds also. Note that, to the best of our knowledge there is no known polynomial time approximation algorithm for upper bounded k-means problem.
C Experiments
We empirically evaluate our combination algorithm for the k-Median objective on benchmark datasets from the UCI Machine Learning Repository, as preprocessed in Almanza et al. (022)) Adult, Diabetes, and Bank. The Adult dataset Dua& & Graff (2017) contains census records, the Bank dataset Moro et al. (2014) contains data points from a marketing campaign, and the Diabctes dataset Strack et al. (2014) contains admission records of diabetic patients. The input points are embedded in Euclidean space, and distances are measured using the & metric. The algorithm is implemented in Python and executed on a Apple laptop with an Apple MI processor, 8 GB RAM, running macOS (Tahoc 26 beta). All source code, logs, and charts are publicly available
(SL) and upper- soper-bounded (Sy) solutions were obtained using greedy heuristics that respect the lower and upper bounds respectively; thus, / 1. Since our combination algorithm is modular, it can operate on any feasible pair (St, Sy) and hence our focus is to evaluate the performance of the combination step itself. independent of the specific heuristics used to generate Sy and St-
Input solutions. The initial
Experimental design. We vary the number of clusters & for E (10, 25, 50, 75, 100). The lower bound L. and upper bound U are derived from the natural cluster size n/k, with buffers of +110% 25%, 50%). Facility pool F of varying sizes (15%, 10%, 20%, 25%} of the input size) are selected randomly from the input points.
hhttp:///gttuub..cm//-mrtt
21

---

Published in Transactions on Machine Learning Research (09/2025)
Distrbttioon of Cost increase Ranto Adult Gataset
Statement 80% the time, Rinal Cose 1188 Nax Heurst e Cost
Modert 100 rersenle
283
120
180
(a) Adult: Costs vs. guarantees
(b) Adult: Distribution of obtained costs
Distibution Statome 85% the time. Final Cost. sce 1.224 Max Heatisti Cest
merral
Bnrress Kall Pritcca (aar
(c) Diabetes: Costs vs. guarantees
(d) Diabetes: Distribution of obtained costs
Dsiibbttion
Bank Dataset
Statement: 90% the time, Final Cont 3. 132 Hax stic Cost lis
aecoalia 1017
322
(e) Bank: Costs vs. guarantees
(f) Bank: Distribution of obtained costs
Figure 5: Left column (a, e) shows the plot of costs of S,, St, our combined solution, and the theoretical guarantee (7Cost (Ssoos((Sstoosttttt cost corresponding to the worst observed gap between the cost our solution and max (Cost(S1), Cost(Su)) Cost(combined)
against the values of k. For our combined solution, the y-axis reports the
Right column (b, d, f): distribution of the ratio mux(Coort(S,,Coott(5.) across all runs.
C.1 Results and Insights
Cost Analysis. Figure reports cost performance across all datasets. The left column (Figure (a, c, e)) shows results as & varies. For each value of k, we run the algorithm with different (L,U) settings and varying the size of the facility pool. The y-axis reports the cost corresponding to the worst observed gap between the cost of our solution and max (S)) Cost(Su)}. We observe that, across all datasets, our algorithm is close to the maximum of the input costs Cost and Cost(Su).
22

---

Published in Transactions on Machine Learning Research (09/2025)
Arg, Mbblaic leaomad for 401 Dycauet
Gap
(a) Adult: violation vs. gap
(b) Adult: average violation heatmap
Hestrage upper board adaa))
Welpoon Noctar Narmakzedd Cop (ENavetts Unlosees
3300000020010 cas
(c) Diabetes: violation vs. gap
(d) Diabetes: average violation heatmap
Aug, Volation Heatmng for Bant Dusestt Wolldoon
1121)
11
(e) Bank: violation vs. gap
(I) Bank: average violation heatmap
Figure 6: Left column (a, c, e): upper bound violation factor as function of the (U/L). Right column (b, d, f): heatmap showing the combined impact of k and (L, U) setting on the violation, on the cost averaged over varying sizes of the facility pool.
The right column (Figure (b, d, f)) shows the full distribution of the ratio (Ss across all runs. The distribution is sharply concentrated near 1, confirming that the cost overhead is minimal in practice. In particular, the combined cost within 1.2 of the cost of maximum of the two input solutions and it is typically 1.1.
Cost(combined)
Thus, the cost of our solution is substantially better than the worst-case theoretical bound.
23

---

Published in Transactions on Machine Learning Research (09/2025)
Upper Bound Violation. Figure f analyzes the violation factor of the upper bound constraint. The left column (Figure 0 (a, e)) plots the violation factor as function of the U/T, and k for all sizes of the facility pool. It can be observed, the violation is within 1.54 in se 80% of the cases. The right column (Figure G (b, d, f)) presents a heatmap that shows the combined impact l and (L,U) setting on the violation, on the cost averaged over varying sizes of the facility pool. It can be observed that the average violation over all the runs never excceds 1.37 all the data sets.
Further, observed the trend that the performance degrades with higher values of k and also with tight gap between L and U. Since & is typically small, violations in practice expected to be small. The latter observation aligns with our theoretical analysis presented in Appendix A. Thus, in practice, violations
remain well below the theoretical bound of (B + 1) in most of the cases.
24


Reviews:
[{"review_id": "oLXdOgBuf7", "reviewer": "Reviewer_H7wK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- Clustering with both lower and upper bounds is important for practical applications. The lower bound constraint, in particular, is difficult to handle in facility location problems due to its combinatorial nature.\n- The algorithm provides a bicriteria approximation guarantee for cost and constraint violation.\n- The computational complexity of the algorithm is very low and practical.\n- Constructing a solution that satisfies both lower and upper bounds from approximate solutions of problems with only one of these constraints is a highly non-trivial task. The algorithm's novelty lies in techniques such as constructing a directed graph and reassigning clients to break cycles.\n-The framework can be extended to various similar types of clustering problems.\n\nWeaknesses\n- The bounds $L$ and $U$ are uniform. (Although this is still a difficult problem, so it may not be a major concern) .\n- Regarding the writing, the results are presented as very general, which makes it difficult to see how much improvement was made over previous research for specific individual cases.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**The Problem Setting**: \nAn instance $I$ is defined by a set of facilities $F$, a set of clients $C$, metric cost $c(i,j)$ for serving a client $j \\in C$ from a facility $i \\in F$,  uniform lower bound $L$ on the minimum number of clients assigned to any open facility,  uniform upper bound $U$ on the maximum number of clients assigned to any open facility, and thethe maximum number of facilities that can be opened. The objective is to find the set of facilities $F'$ and assignments $\\sigma: C \\rightarrow F’$ that minimizes the total service cost.\n$$\n\\min  \\sum_{j \\in C} c(j, \\sigma(j))\n$$\nsubject to\n    $$\n   |F'| \\le k,  L \\le |\\sigma^{-1}(i)| \\le U \\quad \\forall i \\in F'.\n    $$\n i.e., the number of opened facilities must be at most $k$, while also satisfying the lower and upper bound constraints for each opened facility $i \\in F'$.\n\n**Methods and Main Results**: From an instance $I$ of EL Clustering, we obtain the $\\alpha_U$-approximation algorithms for Upper Bounded k-median (UkM)  and $\\alpha_L$-approximation for Lower Bounded k-median (LkM). From these two solutions, the authors propose a non-trivial construction to obtain the approximation solutions for EL clustering, where violation of upper constraints guarantees $(\\beta+1)$-factor and total-costs guarantees 7$\\alpha_U$ + 2$\\alpha_L$ factor. Time complexity is $O(k^3+n)$ time.\n\nWhen integrating two solutions $S_U$ an $S_L$, which are derived from problems with separate constraints, a dependency graph of facility groups called stars is modeled (Algorithm 1). Cycles present in this graph are broken by redefining client assignments, thereby generating an \nalmost-DAG (Algorithm 2). \nFinally, clients are reassigned according to a topological ordering of this almost-DAG in a non-strraigfoward procedures(Algorithms 3 and 4). \n\nThis process constructs an approximate solution that strictly preserves the lower constraints (Lemma 6.2) and only violates the upper constraints with factor $(\\beta+1)$ (Lemma 6.3), while keeping the cost within a constant factor of the optimum (Lemma 6.1 and 6.4).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions\n\n- Can the framework be extended to the non-uniform case, where\n$ L_i$​ and $U_i$​ are different for each facility $i$?.\n\n\nRequest Changes:\n- It would be great to add a table summarizes the approximation ratios and violation rates obtained in the paper for various problems.", "broader_impact_concerns": "N/ A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S4uEUY6PgA", "reviewer": "Reviewer_eQhB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and the proposed method seems to be new and interesting and useful.\nHowever, the paper is not easy to read for nonexperts in constraint clustering.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed a method of combining SU and SI clustering to find a EL clustering with a theoretical guarantee.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- But, it is hard to read by nonexperts of constraint clustering.\n  1. what is \"violation factor\"?\n  2. Whar are $\\alpha_U, \\alpha_L$ approximation in Corollary 3.2?\n  3. What ate 16-factor approximation, 3-factor violation, $O(1/\\epsilon^2)$ approximation algorithm\n- Can the problem be solved by linear programming?  This is typically done by fair clustering.\n- It is hard to read Section 5 even though Section 5 explains the core idea of the proposed algorithm. \n  1. What is 'Star\" in Section 5? \n  2. What is \"yl - the last facility in the sequence\"? What sequence is it? \n  3. It would be good to explain the core idea with a toy example.\n\n- Computation cost $O(k^3+n)$ is only for combination of SU and SL without\n including the cost for obtaining SU and SI. If it is true, this point should be mentioned.\n\n- The main contribution of the proposed algorithm is to combine exsiting SU and SI algrithms to EL clustering. \n  A better title would be \" A novel algorithm to combine SU and SI clusterings to have EL clusterings\" or something like that.\n\n- In appendix B, for each method, it would be good to add references for SU and SI clustering algorithms.", "broader_impact_concerns": "No concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7YyNTM4FgW", "reviewer": "Reviewer_fkZg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper begins with a strong motivation, clearly outlining the practical relevance and importance of the equitable load (EL) clustering   problem.\n2. The proposed solution adopts a modular strategy, which is noteworthy as it allows integration with a range of existing clustering algorithms.\n3. The framework is generalizable beyond the k-median objective and can be extended to clustering formulations such as k-means, k-center, and knapsack median.\n\nWeaknesses:\n1. The final solution violates the upper bound constraint by a factor of β + 1, which may be undesirable in many real-world applications. Additionally, the overall approximation factor is quite large, limiting the method's practical usefulness.\n2. The modular design makes the algorithm heavily dependent on the performance and quality of the subroutines used to solve the upper- and lower-bounded k-median problems.\n3. The paper becomes significantly difficult to follow after Section 2. Section 3, particularly after Corollary 3.2, requires substantial rewriting due to lack of clarity and poor organization.\n4. Section 5 is especially problematic: essential terms such as open facilities, closed facilities, stars, and spokes are used before being properly defined, making the remainder of the paper hard to follow.\n5. There is noticeable repetition in citations and phrasing, especially regarding the modular approach, which detracts from readability and conciseness.\n6. The paper lacks any empirical validation or experimental results to support its theoretical claims, making it difficult to assess its practical viability. \n7. Overall, although the constrained clustering problem addressed in the paper is interesting and well motivated, the current presentation suffers from serious clarity and structural issues. The paper, in its present form, is not suitable for acceptance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper develops an algorithm to solve the k-median clustering problem under both lower and upper bounds on cluster cardinalities. The proposed approach addresses the problem by combining solutions from two separate instances: one that omits the upper bound constraint (relaxes upper bound), and another that omits the lower bound constraint (relaxes lower bound).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As previously discussed, the paper requires substantial revisions before it can be considered for publication. If the following changes are implemented, the submission may become suitable for acceptance:\n1.  Define key terms early: Clearly define terms such as star, star-center, spokes, open and closed facilities before they are used in the algorithmic descriptions.\n2. Rewrite Section 3 (post-Corollary 3.2): Improve structure and clarity in this section. Present the approximation results and their implications more clearly, avoiding repetitive phrasing.\n3. Substantially revise Section 5: This section is currently difficult to follow. Please rewrite with a clearer exposition, provide intuitive explanations of the algorithm, and ensure all figures are explicitly referenced and explained in the text.\n4. Eliminate repetition: Reduce redundancy in the description of the modular strategy and citations throughout the paper.\n4. Add empirical validation: Include experimental results (even synthetic or small-scale) to demonstrate the practical viability of the proposed approach.\n5. Address the impact of upper bound violations and large approximation factors: Discuss when the approximation guarantees are acceptable in practice, and whether the violation factor $\\beta+1$ can be mitigated in real-world scenarios.\n6. Improve overall clarity and tone: Fix grammatical errors, avoid informal language, and ensure consistency in notation and definitions across the paper.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)