Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering

Authors: anna  arutyunova
jan  eube
heiko  röglin
melanie  schmidt
sarah  sturm
julian  wargalla
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 11:40:52

Abstract: As a major unsupervised learning method, clustering has received a lot of attention over multiple decades. The various clustering problems that have been studied intensively include, e.g., the $k$-means problem and the $k$-center problem. However, in applications, it is common that good clusterings should optimize multiple objectives (e.g., visualizing data on a map by clustering districts into areas that are both geographically compact but also homogeneous with respect to the data).  We study combinations of different objectives, for example optimizing $k$-center and $k$-means simultaneously or optimizing $k$-center with respect to two different metrics. Usually these objectives are conflicting and cannot be optimized simultaneously, making it necessary to find trade-offs. We develop novel algorithms for computing the set of Pareto-optimal solutions (approximately) for various combinations of two objectives. Our algorithms achieve provable approximation guarantees and we demonstrate in several experiments that the (approximate) Pareto set contains good clusterings that cannot be found by considering one of the objectives separately.

Main paper: 
 introduction: 
 Clustering is a major unsupervised learning method that is used to find structure in data. It is often described as the process of dividing objects into groups called clusters such that objects in the same cluster are similar and objects in different clusters are dissimilar. There are several mathematical and algorithmic ways to describe a good clustering, but two objectives that correspond to that description for the case of metric clustering are the k-diameter problem and Single Linkage clustering.In the k-diameter problem, we are given a point set P from a metric space and a number k and want to find a partition of P into k clusters that minimizes the maximum diameter of any cluster. This models the first problem: Finding clusters where the objects in the same cluster are similar. This problem can be 2-approximated by well-known algorithms [30, 37] . But are approximate or even optimal solutions for this problem automatically also good for the second half of the description, i.e., ensuring that points in different clusters are dissimilar? Certainly not, as the small example in Figure 1 shows: An optimal k-diameter clustering with k = 2 has radius ∆, but x 2 and x 3 are very close together in this solution. Single Linkage clustering is a linkage method that finds the clustering in which the minimum distance between any two clusters is maximized, i.e., it focuses on the second goal. We refer to the problem of maximizing the minimum inter-cluster distance as the k-separation problem in the following, i.e., Single Linkage is an optimal algorithm for the k-separation problem. In Figure 1 with k = 2, Single Linkage computes the clustering {{x 1 , x 2 , x 3 }, {x 4 }} or the symmetric clustering. Unfortunately, there is an inherent tension between the k-diameter and k-separation problem, even if the points are on the Euclidean line R.In Figure 1 , we could observe that the optimal k-separation clustering is still a very good kdiameter clustering (assuming ϵ to be small). However, one can construct examples where the two cost functions cannot be reconciled: Example 1. For any fixed k ∈ N consider the set X k = {1, . . . , k -1} ∪ A with A = {-x/k | x ∈ {0, . . . , k(k -1) 2 }}. Figure 2 illustrates this for k = 3. Now the only way to obtain a minimum inter-cluster distance of 1 is to use k -1 singleton clusters {1}, . . . , {k -1} and one cluster for A (any other clustering needs to break A and has a separation of 1/k). Notice that this clustering has a maximum diameter of (k-1) 2 since that is the diameter of A. However, the best k-diameter clustering divides the points into intervals of equal length, achieving a diameter of ((k-1) 2 +(k-1))/k = k-1, which is smaller by a factor of k -1.Example 1 demonstrates that the natural goal of clustering is inherently a goal with two potentially conflicting objectives. Our formalization with k-diameter and k-separation is an example of a bi-objective clustering problem. This is only one motivation for studying multi-objective (or bi-objective) clustering. Clustering with respect to multiple objectives simultaneously or based on different metrics arises naturally in applications (we cite a selection of works at the beginning of the related work section). Yet the theoretical study of multi-objective clustering problems is, so far, very limited. We consider the case of bi-objective clustering and study combinations of various clustering objectives with the possibility of optimizing each over its individual metric.Objectives We restrict to the case where centers are chosen from the point set. This is common for k-median, but uncommon for k-means. We leave the extension where centers can be chosen from an ambient metric space to future work. So let (P, d) be a metric space. Given C ⊂ P with |C| = k and an assignment σ : P → C we define the following objective functions: Notice that in contrast to standard definitions, here we need an assignment function because our solutions are trade-offs and may not necessarily assign points to closest centers (for k-diameter and k-separation we do not need the centers but only the partitioning that σ induces; we use the same notation here for convenience and introduce additional notation in the respective technical sections). Each objective induces an optimization problem when we fix the number of clusters k ∈ N we want to obtain 1 . The k-separation problem is a maximization problem, all other objectives are to be minimized, i.e., the aim is to compute a set C with k centers and an assignment function σ with σ -1 (c) ̸ = ∅ for all c ∈ C such that the respective objective function is as low as possible. All the minimization problems are NP-hard and also NP-hard to optimize to arbitrary precision [17, 31, 40, 44] . On the positive side, approximation algorithms with small constant factors are known for all the minimization problems mentioned, see Table 1 (all numbers are for the general metric case, including k-means).The k-separation maximization problem can be solved optimally by running the well-known Single Linkage algorithm until the given number k of clusters is left.We have two different use cases: 1) Simultaneously optimizing a well-known kclustering minimization problem together with the conflicting k-separation maximization problem.2) Optimizing two k-clustering minimization problems simultaneously. In both cases, we allow to choose different metrics for each objective. As an example for 2), imagine that we want to visualize data on a map by clustering districts into larger regions. Then regions should be homogeneous with respect to the data but at the same time also geographically coherent on the map, not stretching out too far. For this application we can use as the first metric the data-based metric and as the second metric the geographic distance between regions on the map. Then we can choose an objective, e.g., k-center, and find a good trade-off when optimizing k-center with respect to the two objectives. This idea is discussed in more detail in Section 3.2.Multi-objective Optimization and Pareto Sets Both use cases can benefit from the same tool box of multi-objective optimization. Standard approaches are optimizing a weighted sum of the objectives, or limiting one objective and optimizing the other (leading to a constrained clustering problem), or computing/approximating the Pareto front. We follow the latter approach and focus on algorithms to approximate the Pareto front of bi-objective clustering problems. Let us first define this concept formally: Given two metrics d 1 , d 2 on X and two objectives f 1 , f 2 ∈ {rad, diam, med, mean, msr, sep}, a solution (C, σ) is dominated by a solution (C ′ , σ ′ ) if the following is true for both i = 1, 2:f i (C ′ , σ ′ , d i ) ≤ f i (C, σ, d i ) if f i is a minimization objective and f i (C ′ , σ ′ , d i ) ≥ f i (C, σ, d i ) if f iis a maximization objective, and in addition, for i = 1 or i = 2, the inequality is strict. A solution (C, σ) is called Pareto-optimal if it is not dominated by any other solution. We denote by P the set of all Pareto optimal solutions and call P the Pareto set or Pareto front.Notice that by definition the Pareto front contains a solution (C i , σ i ) optimizing objective f i for i = 1, 2. Since all aforementioned minimization objectives are NP-hard, we therefore cannot compute the Pareto fronts exactly in polynomial time unless P = NP. Instead we design algorithms for computing approximate Pareto fronts in the following sense: Given α = (α 1 , α 2 ) ∈ R 2 , a set P α is an α-approximate Pareto set if the following is true: For every Pareto-optimal solution (C, σ) ∈ P, there is a solution (C ′ , σ ′ ) ∈ P α that is an α-approximation to (C, σ), i.e., f i (C ′ , σ ′ , d 1 ) ≤ α i f i (C, σ, d i ) for i ∈ {1, 2} if f i is a minimization objective and f i (C ′ , σ ′ , d 1 ) ≥ (1/α i )f i (C, σ, d i ) for i ∈ {1, 2} if f i is a maximization objective. Figure 3 shows two examples of approximate Pareto sets. In 3a) the trade-off is between k-separation and k-means (use case 1). This is discussed in Section 3.1. In 3b) both objectives are chosen as k-center, but with two different metrics that arise from a map design question discussed in Section 3.2 (use case 2). In both pictures the area dominated by a solution lies to the right and above the corresponding point.While other approaches for multi-objective optimization (like optimizing a weighted sum of the objectives or solving a constrained clustering problem) produce a single trade-off of the objectives, an important advantage of the approximate Pareto front is that it consists of a diverse set of trade-offs. This is beneficial for data analysis because it offers more information and flexibility to the data analyst.In particular, an approximate Pareto front contains for any weighting of the objectives an approximately optimal solution and often, in addition to this, also other interesting solutions. We develop and analyze algorithms for computing approximate Pareto fronts. We also demonstrate experimentally the usefulness of approximate Pareto fronts and our algorithms in different applications. There is a large body of literature on multi-criteria optimization problems in different contexts (see, e.g., the book of Ehrgott [23] ). A common approach is to compute or approximate the Pareto set because only Pareto-optimal solutions constitute reasonable trade-offs. If the Pareto set or its approximation is small, it can be presented to a human decision maker or used in some other post-processing step. For many multi-criteria optimization problems, algorithms for computing the Pareto set have been developed (e.g., for the multi-criteria shortest path problem [19] and the bi-criteria network flow problem [48] ) The running time of these algorithms is usually polynomial in the output size, i.e., they are efficient if the Pareto set is small. A drawback of this is that Pareto sets can often be of exponential size in the worst case. To obtain more efficient algorithms and to reduce the size of the output, approximate Pareto sets have been studied extensively.Papadimitriou and Yannakakis showed that there always exist approximate Pareto sets of polynomial size and they showed that an α-approximate Pareto set [49] for a problem can be computed efficiently if and only if a certain variant of the problem, called the gap problem, can be solved efficiently.Related Work on multi-objective clustering Heuristics for approximating Pareto fronts for clusterings are used in applications. Popular techniques include, e.g., genetic algorithms [24, 42] , multi-objective particle swarm optimization [10, 14] , evolutionary algorithms [36, 47] , and combinations of k-means and fuzzy c-means [9] . All these heuristics have in common that they come without a guarantee on the approximation factor. We cannot review all the literature in this area and focus on what we perceive as most related.The only work studying the same scenario is a paper by Alamdari and Shmoys [5] who discuss the combination of k-center and k-median and give, following the above definition, an algorithm that computes a (4, 8)-approximation of the Pareto front. Their algorithm uses an LP rounding approach based on a k-median LP with an additional side constraint that restricts the radius of clusters to a given number L. The algorithm uses an optimal (fractional) solution to this LP and rounds it to an integral solution, hereby increasing the radius to 4L and the k-median cost to 8 times the LP cost.The general approach has some resemblance with our findings in Section 2.2 (and Supplementary Section B.3), but it is based on the LP rounding algorithm by Charikar et al. [12] , while we adapt the primal dual algorithm by Jain and Vazirani [41] . We achieve an incomparable approximation factor of (9, 6 + ϵ). Alamdari and Shmoys also give an example that shows that the two objectives k-center and k-median cannot be optimized simultaneously in general, making a similar point as we do in Example 1 showing that at least one of the objectives can at best be Ω( √ n)-approximated.Davidson and Ravi [20] discuss the combination of k-means and must-link and cannot-link constraints.As we discuss in the introduction and in Lemma 3, enforcing a certain separability translates directly into must-link constraints. However, [20] is mostly concerned with NP-hardness results (which stem mostly from cannot-link constraints) and reformulating constraints in a computationally more feasible way. Our focus is on the computationally very efficient Single Linkage / must-link constraints and the computation of Pareto optimal solutions.In Section 3.1 (and Section C.1), we evaluate if the usage of orthogonal objectives can improve the performance of clustering with respect to recovering a ground truth clustering. A similar approach is evaluated by Handl and Knowles in [35] . The first objective studied there is a k-means/k-median type objective called deviation. The second objective is based on nearest neighbors and evaluates the fraction of points that satisfies that the point is in the same cluster as its nearest neighbor. This has a similar purpose as our use of separation in Section 3.1, and also leads to improved F-measures. The focus of that work is still different as we focus on provable approximations of the Pareto front.For the evaluation in that same section, we use normalized mutual information scores following Fred and Jain [27] . In that paper, the idea is to combine multiple clusterings into one clustering in order to obtain more robust clusterings. The authors use a clustering ensemble of different solutions computed by k-means and then let their combination be guided based on the normalized mutual information score. The focus of that work is different since we aim to produce an informative ensemble while Fred and Jain aim at combining an ensemble into a single robust clustering. 
results: 
 We provide algorithms to compute the approximate Pareto set for most combinations of two clustering objectives f 1 , f 2 ∈ {rad, diam, med, mean, msr, sep}. To compute the approximate Pareto set we make use of the variety of approximation algorithms which optimize over one of the clustering objectives. This includes the 2-approximation for k-center/k-diameter by Hochbaum and Shmoys [37] which we adapt to compute an approximate Pareto set for the combination of f 1 ∈ {rad, diam, sep} and f 2 ∈ {rad, diam}. We further incorporate the radius/diameter in the (6 + ϵ)-approximation for k-median (also yielding an O(1)-approximation for k-means) by Jain and Vazirani [41] to obtain an approximate Pareto set for the combination of f 1 ∈ {rad, diam} and f 2 ∈ {med, mean}. We adapt the (3 + ϵ)-approximation for k-min sum radii by Buchem et al. [11] to deal with clusters instead of points such that it can be combined with k-separation. For the combinations of f 1 = sep and f 2 ∈ {med, mean} we use existing algorithms to compute a solution which optimizes f 1 and a solution which optimizes f 2 and combine them to a good solution for both objectives, similar to the nesting technique described by Lin et al. [46] . Lastly for the combinations of f 1 , f 2 ∈ {med, mean} we use the result on convex Pareto sets by Diakonikolas [22] . All of these adaptions are straightforward and we mainly follow the existing work. For the computation of the approximate Pareto set for f 1 , f 2 ∈ {rad, diam} we furthermore design a new algorithm with improved running time which differs significantly from the naive implementation of the Hochbaum and Shmoys [37] adaptation.We complement these results by providing instances where it is not possible to find solutions which simultaneously approximate k-separation and any of the minimization problems to constant factors. We see this for k-separation and k-diameter in Ex. 1 above, it works analogously for k-center. For k-median we analyze a similar example in Obs. 11, k-means works analogously. For k-separation and k-MSR, the example can be found in Obs. 21. This highlights the advantage of Pareto fronts which allow for a trade-off between two opposing clustering objectives. In the following we explain our results and techniques in more detail.Single Linkage is known to have undesirable properties for practical applications, in particular chaining effects. Yet its underlying idea -creating separated clusters -makes a lot of sense intuitively.In this set of results, we investigate the combination of Single Linkage, i.e., the maximization of the k-separation objective, with algorithms that aim to construct good clusters with respect to various popular k-clustering criteria. The idea is that the clustering may benefit from a certain extent of cluster separation without the negative effect of using only Single Linkage to obtain the solution.In Section 3.1 we exemplify the benefit of this idea by a practical evaluation of the k-separation / k-means combination. There we find that ensuring a small amount of separability and then running k-means++ yields good results with respect to recovering a ground truth clustering in our experiments. = 9 + ϵ [16, 4]. k-separation k-center k-diameter k-median k-means k-MSR k-sep. (1, 1) (1, 2) (1, 2) (1, 2 + δ 1 ) (1, 4 + 4 √ δ 2 + δ 2 ) (1, 3 + ϵ) proofThm. 5 Thm. 9 Thm. 7 Thm. 12 Thm. 17 Thm. 24Techniques The k-separation objective is friendly in the sense that we know exactly how optimal solutions look like. First observe that in any optimal solution, the objective value equals the distance of two points in different clusters. This means that there are only Θ(n 2 ) possible optimal values. And if we fix a value ∆ to be the desired separation, then this means that all points x, y with d(x, y) < ∆ have to be in the same cluster because otherwise the objective is automatically below ∆. And if we transitively merge all pairs x, y with d(x, y) < ∆, then we get a solution with objective value ≥ ∆. So it is well characterized how an optimal k-separation solution looks like (also see Lemma 3). For f 2 = rad or f 2 = diam, we also have that the optimum value of a solution is a pairwise distance between two points. Thus, there are also at most O(n 2 ) possible values that f 2 can take. There is a well-known algorithm due to Hochbaum and Shmoys [37] that for any given radius R (or diameter) can produce a solution with at most double that value or prove that no solution with value R exists.We adapt this algorithm to work on the above clustering with Separation ∆ as input. The algorithm is similar to the original work by Hochbaum and Shmoys. By iterating through all pairs of possible separation and possible radius/diameter values, we obtain the (1, 2)-approximate Pareto set. The details are discussed in Section A.2 of the supplementary material.When combining sep with f 2 = med or f 2 = mean (Supplementary Section A.3), we still know that the separation value ∆ is one of O(n 2 ) candidates. We use the above clustering with separation ∆ and decide which clusters to merge further based on an approximate clustering with respect to f 2 . For this purpose we use the nesting technique described by Lin et al. [46] in the context of approximation algorithms for hierarchical clustering. Since we need an approximate clustering with respect to f 2 , the quality of our Pareto set depends on the approximation ratio of the algorithm for f 2 .Finally, we combine sep with msr. This is the only place where we study msr as it is less common than the other clustering objectives. It is also the only objective where we deviate from the rule that clusters have to have = k clusters and allow < k clusters. We study it because it seems more aligned with k-separation than the other objectives. However, Obs. 21 reveals that also k-separation and k-MSR cannot be approximated simultaneously. In order to approximate the Pareto front, we adapt the very recent state-of-the-art algorithm for k-MSR approximation from [11] to our setting. That algorithm has an approximation ratio of 3 + ϵ and indeed, we show how to compute (1, 3 + ϵ)approximate Pareto fronts. Buchem et al. [11] give an intricate primal-dual algorithm for the k-MSR problem. Our general idea follows the above themes: We iterate through all possible separation values ∆, obtain a clustering with separation ∆, and then compute an approximate k-MSR solution. However, for this to work we need to adapt the algorithm to cope with clusters instead of points. Similar to the adaption of the algorithm by Hochbaum and Shmoys the input now consists of clusters, and this needs to be taken into account when trying to cover them with balls. We discuss this in the supplementary material in Sec. A.4.Now we turn to combinations of popular k-clustering minimization problems. The second row links to the proof in the supplementary material.Techniques. The k-center objective has the already mentioned property that there are at most O(n 2 ) possible objective values, one for each pairwise distance in the data set. This also directly limits the size of the resulting Pareto Set when combining two k-center or k-diameter objectives by O(n 2 ). This is tight since we were able to provide an instance where the optimum Pareto set has indeed a size of Ω(n 2 ) (Supplementary Section B.2). However it can be proven that there always exists a (2, 2)-approximation of the Pareto front of size O(n).We adapt a well-known 2-approximation algorithm due to Hochbaum and Shmoys [37] . A straightforward adaption of this algorithm would iterate through O(n 4 ) pairs (r 1 , r 2 ) of possible radii and check for each of them if a maximal independent set of size at most k can be found in an appropriate threshold graph. While this would result in a running time of O(n 6 ), we improve the running time by observing that only certain pairs (r 1 , r 2 ) need to be checked (in total O(n 2 ) many) and by updating the threshold graph dynamically. While updating the threshold graph can have a time complexity of up to Ω(n 2 ) in certain iterations, we were able to use a suitable potential function to show that the amortized time needed to update the graph lies within O(n) per iteration. Hereby we show that we can compute the approximate Pareto set P (2,2) in time O(n 3 ). The algorithm and its analysis also work for k-diameter, giving the same guarantees. For more details we refer to Section B.1 of the supplementary material.To combine k-center with k-median and k-means (possibly with different metrics), we adapt the primal dual algorithm due to Jain and Vazirani [41] . Alamdari and Shmoys [5] adapt the approximation algorithm by Charikar et al. [12] , which leads to a (4, 8)-approximate Pareto set. For recent algorithms [4, 15, 16] , incorporating radius requirements does not seem easily possible.The primal dual algorithm gives a (6 + ϵ)-approximation guarantee for k-median and a 54approximation guarantee for k-means (the paper only states 108, but that is because the k-means problem is considered in R d there, while we study it in the setting where centers are chosen from the input point set. As [4] also observe, the guarantee then improves to 54.) The primal dual algorithm is based on an LP formulation where variables x ij indicate that point j is assigned to center i. The adaptation starts by fixing a radius R and removing all x ij for which d(i, j) > R. It then follows the proof of [41] to first obtain an algorithm for approximating facility location and then obtaining a k-median (or k-means) solution by combining two solutions: one with < k clusters and high cost and one with > k clusters and small cost. In the combination step we have to ensure that the radius stays bounded (see Lemma 47) . We can ensure a 9-approximation with respect to the radius while keeping the original approximation factors for k-median/k-median from [41] . To extend the results to k-diameter, we use that the diameter is at most twice the radius. This standard observation transfers the results for rad with med and mean to diam.In the previous sections we have enumerated over a candidate set that contained all Pareto-optimal solutions and used this enumeration to compute approximately optimal solutions. This is no longer feasible here because the Pareto set is too large: Theorem 48 in the supplementary material shows that the combination of med and mean both with the same Euclidean metric can lead to Pareto sets of exponential size. Similar examples can be constructed for A possible approach to compute an approximate Pareto set is due to Papadimitrou and Yannakakis [49] . They showed that there always exists an ϵ-approximate Pareto set whose size is polynomial in the input size and 1 ϵ ′ where ϵ = (1 + ϵ ′ , 1 + ϵ ′ ). There is a polynomial algorithm to construct such an ϵ-approximate Pareto set if and only if one is able to solve the following problem in polynomial time: Given the instance and b 1 , b 2 ∈ R, find a solution s with f i (s) ≤ b i for i ∈ {1, 2} or report that there is no solution s with (1 + ϵ ′ )f i (s) ≤ b i for i ∈ {1, 2}. Unfortunately, for the combinations of the objectives med, mean it is unknown, whether this problem can be solved efficiently. We leave this as an open problem.f 1 = f 2 and f 1 ∈ {med, mean} if d 1 ̸ = d 2 .An alternative to approximate Pareto sets is to consider another subset of the Pareto set, namely the set of supported Pareto-optimal solutions, i.e., the set of solutions that are optimal for a weighted sum of the objectives. For two minimization objectives f 1 and f 2 , a solution (C, σ) is a supported Paretooptimal solution if there exist weights w 1 , w 2 ≥ 0 such that (C, σ) is a solution for the objectivew 1 f 1 + w 2 f 2 with minimum value. For a solution (C, σ) let F (C, σ) = (f 1 (C, σ), f 2 (C, σ)) and F (P) = {F (C, σ) | (C, σ) ∈ P}.The supported Pareto-optimal solutions are exactly the solutions that form the vertices of the convex hull of F (P). Hence, we will call the set of supported Paretooptimal solutions the convex Pareto set in the following. Diakonikolas [22] has also introduced the notion of approximate convex Pareto sets. For α = (α 1 , α 2 ) ∈ R 2 we say that a set of solutions CP α is an approximate convex Pareto set if for any solution (C, σ) there is a a convex combination of solutions in CP α that is an α-approximation to (C, σ). In this context we always assume α 1 = α 2 and therefore just write CP α1 instead of CP (α1,α2) in the following. Diakonikolas [22] showed that an (F)PTAS for the convex Pareto exists if there is an (F)PTAS for optimizing weighted sums of the objectives. Based on this, we obtain the following theorem. Theorem 51. Given a finite set P, metrics d 1 , d 2 on P and two objectives f 1 , f 2 ∈ {med, mean}. Let ϵ > 0. Then we can compute an (δ + ϵ)-approximate convex Pareto set CP δ+ϵ in time that is polynomial in the input size and 1 ϵ , where δ = 2.67059 if f 1 = med and f 2 = med, and δ = 9 + ϵ if f 1 = med and f 2 = mean or f 1 = mean and f 2 = mean. The size of this set |CP δ+ϵ | is also polynomial in 1 ϵ and |P |.1 • med(C, σ, d 1 ) + w 2 • mean(C, σ, d 2 ) = w 1 • p∈P d 1 (p, σ(p)) + w 2 • p∈P d 2 2 (p, σ(p)) = p∈P w 1 • d 1 (p, σ(p)) + w 2 • d 2 2 (p, σ(p)). Thus all we have to do in order to apply the algorithm to our objective is to show that c(i, j) = w 1 • d 1 (i, j) + w 2 • d 2 2 (i, j) fulfills the necessary property, which is done in the following:c(i, j) = w 1 d 1 (i, j) + w 2 d 2 2 (i, j) = w 1 (d 1 (i, k) + d 1 (k, l) + d 1 (l, j)) + w 2 (d 2 (i, k) + d 2 (k, l) + d 2 (l, j)) 2 ≤ w 1 (d 1 (i, k) + d 1 (k, l) + d 1 (l, j)) + 3w 2 (d 2 2 (i, k) + d 2 2 (k, l) + d 2 2 (l, j)) ≤ 3(w 1 d 1 (i, k) + w 2 d 2 2 (i, k) + w 1 d 1 (k, l) + w 2 d 2 2 (k, l) + w 1 d 1 (l, j) + w 2 d 2 2 (l, j)) = 3(c(i, k) + c(k, l) + c(l, j)).Therefore we also achieve the factor 9+ϵ ′ for the combined cost function using the algorithm in [4] .3. This works analogously to 2., by setting c(i, j) = w1 • d 2 1 (i, j) + w 2 • d 2 2 (i, j) instead.The theorem now follows directly from Lemma 53 and the factor achieved by our scheme.C.1 Improving k-means++ by combination with separationWe test the approach to combine k-means with separation presented in Chapter A.3 on data sets with ground truth inputs [2, 26, 6, 1, 3, 34, 32, 33] . We hope to improve the quality of the solution found by k-means++ by a combination with Single Linkage. We evaluate the best solution (compared to the ground truth) found by our approach in comparison to solutions found by k-means++ [8] and Single Linkage [52] . Since all tested data sets are provided with a ground truth, we fix the number of clusters k for the approximate Pareto set to be the desired number of clusters in the ground truth.Algorithm. For every data set, we compute the approximate Pareto set for the desired number of clusters as follows. Recall that for a data set of size n there are only O(n 2 ) possible values for the separation. We compute these values in time O(n 2 d) and sort them in increasing order in time O(n 2 log(n)). Here d is the dimension of the data set. Starting with separation 0, we increase the separation in every step to the next largest value. Suppose the separation is ∆ in the current step, then we merge all points whose distance is at most ∆. This can be done efficiently via a Union Find data structure. Since the resulting clustering may have more than k clusters, we have to reduce the number of clusters to k. For data sets in R d and the k-means objective, one can replace every cluster by its centroid weighted by the number of points in the cluster and then cluster these weighted centroids instead of using the nesting technique of Lin et al. [46] for general metrics. Instead of choosing the theoretically best approximation algorithm for k-means, we use k-means++ [8] to cluster the centroids as it is known to be fast Evaluation. We compare the clusterings in the approximate Pareto set to the ground truth. For this purpose we compute the Normalized Mutual Information, Rand Index, and F β -scores for β = 0.5, 1, 2. We briefly recall their definition below. For every measure we pick the clustering in the approximate Pareto set that has highest value with respect to this measure. We compare our results with two variants of k-means++ and Single Linkage. In the first variant we do not fix the number of clusters, i.e., k-means++ and Single Linkage are performed for every k = 1, . . . , n and we compute the highest values achieved by these clusterings. In the second variant we fix k to the desired number of clusters in the ground truth and compute the respective values for all measures. Since k-means++ and our algorithm are randomized, the depicted values are the average of the maximum values achieved in 20 runs. The results are in Figure 11 .Data Sets. We tested the algorithms on the following data sets.• Iris [26] : 150 points, d = 4, k = 3• Dry Bean [2] : 13611 points, d = 16, k = 7• Rice [1] : 3810 points, d = 7, k = 2• Wine [3] : 178 points, d = 13, k = 3• Optdigits [6] : 5620 points, d = 64, k = 10• 2d-4c-no3 [34] (Figure 7a ): 1123 points, d = 2, k = 4• 2d-10c-no3 [32] (Figure 7b ): 3359 points, d = 2, k = 10• 2d-10c-no4 [33] (Figure 7c ): 3291 points, d = 2, k = 10 Results. The results show that for all data sets except rice and all measures the best solution in the approximate Pareto set has a higher value than the solutions found by Single Linkage and k-means++ individually for the same number of clusters. In some cases k-means++ and Single Linkage provide better results when allowing different numbers of clusters. Especially Single Linkage does provide better results when we allow for more clusters, since it is sensitive to outliers. We see for example on the data set 2d-10c-no4 in Figure 8 that Single Linkage reconstructs all of the larger clusters when performed for an appropriate separation value and performs better than k-means++ with k = 10 (Figure 8a ). However the number of clusters is large (k = 85) since there are some outliers which are in separate clusters. If we perform Single Linkage for k = 10 we see that the result is two large clusters containing most of the points and 8 clusters with at most 2 points each. The best solution in the approximate Pareto set (Figure 8d ) mostly coincides with the solution found by Single Linkage in Figure 8c , however it has only 10 clusters. A similar behavior can also be observed on the data sets 2d-4c-no3 and 2d-10c-no3 in Figure 9 and Figure 10 .Based on our experiments the combination of k-means++ and Single Linkage can be useful to• reduce the number of clusters found by Single Linkage or • improve the quality of the k-means++ solution.On all data sets that are not synthetic, the best result in the approximate Pareto set has a small separation, as we see in Figure 12 . Therefore we assume that it is sufficient to execute the algorithm for small separation values instead of computing the whole approximate Pareto set to improve the quality of the solution. Notice that on the data sets rice, wine, and optdigits the best solutions on the approximate Pareto set for some measures are the ones with smallest separation. However it does not necessarily coincide with the solution found by k-means++ and in fact performs better with respect to NMI, RI, and F β -scores. For a visualization of NMI on the approximate Pareto set we refer to Figure 13 . In Figure 14 one can see the variance of the measures for k-means++ and the approximate Pareto set.Resources and running time. The experiments were performed on a machine with a 2.7GHz AMD Ryzen 7 PRO 6850U processor and 32GB RAM. The source codes are in C++ and available at https://github.com/algo-hhu/paretoClustering in folder kMeans_SL. The first draft of the k-means++ algorithm and the Union Find data structure were produced using ChatGPT 4.0, but then adapted and extended for our needs. The code was compiled using g++ version 11.4.0 with optimization flag -O2. Since the experiments are performed for a proof of concept and are not optimized for running time, the running time was not tracked. The computation of the approximate Pareto set and the evaluation with respect to all measures took at most 15 minutes per data set.Measures. The following measures are used to evaluate the similarity between the ground truth and the computed clustering. The measures take values in [0, 1], where a value of 1 is achieved when the computed clustering matches the ground truth. For a detailed survey on such measures we refer to [54] . Let (C, σ) be the computed clustering and (C * , σ * ) be the ground truth. For i ∈ C, j ∈ C * let• P ij = {p ∈ P | σ(p) = i, σ * (p) = j} be the set of points assigned to center i by the computed clustering and j by the ground truth, We combine their definition with the more general definition of an F β -score in binary classification by van Rijsbergen [53] and obtain the F β -score of a cluster i and j asF β (i, j) = (1 + β 2 )Prec(i, j) • Rec(i, j) β 2 • Prec(i, j) + Rec(i, j) .The F β -score of (C, σ) is then defined as F β (C, σ) = 1 n j∈C * |P * j | max i∈C F β (i, j).In this section we use our algorithm for combining two different k-center objectives to cluster the 400 German districts by their median income. Our goal is to compute clusters of districts of similar median income that are also geographically compact. Hence, we use as second objective function the geographic distance between the districts. This way it can be ensured that only districts close to each other get clustered together. This results in clusters that actually correspond to meaningful regions which could help identifying and analyzing regional inequality within a country.To calculate the difference between the monthly median incomes of two states we used the information of the German "Bundesagentur für Arbeit" [29] from December 31, 2022. To calculate the distance between the districts we obtained a geojson file containing their border [21] , calculated the centers of mass where we interpreted the shapes as regular polygons (as the curvature of the earth should not have too much influence on that scale), and then calculated the distance between those centers while accounting for the curvature of the earth.Figure 15 provides an overview on the income structure in Germany. We will mainly discuss the details of the results for the case that k = 16 (the number of states in Germany). The respective Pareto curve is shown in Figure 16 . However, the behavior for other choices of k is similar, as can be seen in Figure 17 .In total the Pareto curve contains 38 different solutions, where the first optimizes the geographic radius of the clusters as much as possible and the 38-th minimizes the income difference. We will have a closer look at the 10-th and 15-th solution. We consider solutions that appear relatively early in the Pareto front because the geographic radius increases to 300 or even 350 kilometers relatively early on the Pareto front. Clusterings with such a large radius are not interesting because the air-line distance between Kiel (which lies in the north of Germany) and Munich (which lies in the south) is less than 700 kilometers, meaning that the solutions appearing later in the Pareto front cluster together districts that are far apart. In Subfigure 19b the 10-th Pareto solution is depicted. On the left the clusters are colored by the average income of the respective districts and on the right in colors that are easier to distinguish but have no intrinsic meaning. One can see that multiple clusters are next to each other that barely differ in their income which is not surprising because if the algorithm would cluster them together the geographic distance between the different parts of the cluster would get too large. At the same time we have some regions where two or more clusters basically cover the same geographic region and split up the districts depending on the respective median income in these districts. Despite all of this, the left image gives us a very good idea how the incomes differ in different regions of Germany. This is also interesting because the geographic radius of this clustering is roughly 196 kilometers and the maximum income difference between a district and its respective center is 463C per month. Even though the latter value allows the algorithm to cluster districts together that have a large income difference (as a comparison the maximum income difference is roughly 1900 C) the clusters appear to be reasonable and meaningful.To get a better idea about the quality of the chosen Pareto solution in Figure 19a , the clustering produced by a k-center 2-approximation that only considers the income difference as a metric as well as a similar clustering for the geographic distance metric are depicted in Figure 19c . As expected for the income-based clustering the clusters are split up over the entirety of Germany. If one depicts them in the colors corresponding to the median income of the districts in the cluster, one basically ends up with a modified version of Figure 15 where the income levels have been discretized to 16 different levels. On the other hand, in the geography-based clustering districts with very different median income have been clustered together. As a result the median incomes are very similar for many pairs of clusters (it is almost the average over the entirety of Germany) and the information where a wealthy region starts and a not so wealthy region ends gets obscured.In Figure 20 the 15-th Pareto solution is depicted. The geographic radius of this solution is 245 km and the maximum income difference between a district and its center is 321 C. Indeed one can observe that in the map which colors the clusters according to their average median income a lot more details are visible. However at the same time, the clusters are a lot less compact often being split up into multiple regions or having holes in which the contained districts are part of another cluster. The resulting images also give an idea why we did not look at Pareto solutions prioritizing the income metric even more since already in this solution the clusters do not really resemble something that a person would intuitively describe as a region. Another example for an application of combining two k-center objectives with different metrics is to cluster the tide gauge stations of the Permanent Service for mean Sea Level (PSMSL) [50, 39] dataset. This dataset consists of 1581 tide gauge stations all over the world, most of them located on coastlines. Figure 21 shows their positions. Each of those stations measures the sea level at its respective location on a monthly basis, resulting in 1581 time series, some of which date back into the 19-th century.Our goal is to cluster stations together that show similar behavior of the sea level, but at the same time we also want clusters to be geographically close to each other. In this way, we hope to be able to identify regions where the sea level behaves similarly and find a representative set of stations, that uses fewer stations, but does not loose a lot of information. It might also be helpful in order to achieve a more evenly spread out set of stations since the northern hemisphere is over-represented in terms of concentration of the stations in comparison to the southern hemisphere.We clustered the stations according to their geographic distance and the distance of the corresponding time series. For the geographic distances, we used the Euclidean distance between the stations, while accounting for the curvature of the earth. For the distance between the time series we used the mean over the pairwise difference between two time series, namelyEQUATIONi -ti ,where t (1) , t (2) are two time series with |t (1) | = |t (2) | = l. For both distance measures, we used the k-center objective.Unfortunately, the time series do not all cover the same time span and many of them have missing periods of data points due to a lot of different reasons (e.g., damage of the respective station, stations were not all built at the same time). Since our distance measure is not metric under these circumstances, which is a crucial part of our analysis, we conducted our experiments on a synthetic dataset using the ORAS5 [18] global ocean reanalysis, which simulates the sea level beginning in 1958 until today on grid coordinates all around the world. We created time series similar to the PSMSL dataset by mapping the coordinates of every station to the geographically closest grid point of the simulation that lies in the sea. With this method, we were able to produce 1581 complete time series, dating from January 1958 until December 2022. Since we are only interested in the change in sea level height, we normalized all time series by subtracting their mean value.We considered the clustering for k = 150. In total, the approximate Pareto set contains 106 solutions.Figure 22 shows the approximate Pareto curve. The first Pareto solution optimizes for the time series metric, while the 106-th solution minimizes for the geographic distance. The 54-th Pareto solution is highlighted in red, since we are using it in later figures as example for a Pareto solution that balances both objectives quite well. One can see that by only moving by one or two solutions in the Pareto curve, there can be major improvements on one metric while the loss on the other metric is relatively small in comparison, especially on its border. Therefore the Pareto solutions might even be interesting in the case, where one is mainly interested in one of the metrics.In the following, we will compare the 54-th Pareto solution to the clusterings, that either only consider the time series based clustering, or only consider the geography based clustering. The clusterings we compare to have been computed without any knowledge of the second objective. They do not necessarily coincide with the two extreme solutions in the approximate Pareto set. We compare those two solutions to the 54-th solution of our Pareto curve, which is located on the middle of the Pareto curve and therefore should be a good trade-off between the different objectives. One can see a visualization of the three clusterings in Figure 23 . For more details, Figure 24 shows the region of Europe (since there is a high concentration of stations there). The Pareto solution and the geographic solution both show quite compact clusters, while the clusters of the time series based clustering span bigger distances and are also overlapping each other. One can also see, that for the time series based clustering, the regions that have a very high concentration of stations usually also contain more cluster centers than the regions with a low concentration of cluster centers, while in the Pareto solution and especially in the geography based clustering, the centers are more evenly distributed over the globe.Figure 26 shows the clusters with the largest geographic distance for the geography based solution, the time series based solution, and the 54-th approximate Pareto solution. It is easy to see that both the geographic and the Pareto clustering are quite compact, and all points of the cluster are located in the same geographic region, while the points of the time series based clustering span over three different oceans.Analogously, Figure 25 shows the worst cluster with respect to the time series for the same three clusterings. One can see that in the Pareto clustering and the time series based clustering, the red center curves seem to be relatively good representatives of the other curves, while in the geography based clustering there are curves that obviously do not match the center curve at all. Table 7 confirms these findings, and also shows that these effects are not only restricted to the worst cluster in a solution, but also visible in the mean of the radii over all clusters. Like before, for both objectives the mean radius of the Pareto solution is much closer to the mean radius of the clustering that is optimized for the respective objective than to the other one.Resources and running time. The experiments were performed on a machine with an 2,4 GHz Apple M2 processor and 24 GB RAM. The source codes are in Java and were compiled using oracle OpenJDK version 21.02. The computations of the Pareto sets took less than a minute. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
applications and experimental evaluation: 
 We implemented algorithms for two objective combinations and tested them on different applications.The source code can be found at https://github.com/algo-hhu/paretoClustering.We test the approach to combine k-separation with a conflicting objective. As that second objective, we choose k-means. Since the data sets used in our experiments are from R d , we do not use the algorithm described in Sec. A.3 for general metrics but a variant of it which is tailored to R d and allows centers from R d instead of only P . It is described below. The Euclidean metric is used for both sep and mean. We test this algorithm on data sets from R d with available ground truth. We fix the number k of clusters to be the desired number of clusters in the ground truth. All data sets were downloaded from freely available sources, see Table 4 for information on the data sets.Algorithm. For every data set, we compute the approximate Pareto set for the desired number of clusters as follows. Recall that for a data set of size n there are only O(n 2 ) possible values for the separation. We compute these values in time O(n 2 d) and sort them in increasing order in time O(n 2 log(n)). Starting with separation 0, we increase the separation in every step to the next largest value. Suppose the separation is ∆ in the current step, then we merge all points whose distance is at Prototypical desired behavior. Consider Fig. 4 . It shows the data set 2d-10c-no4 by Handl and Knowles [33] , which is a synthetic data set with 10 clusters. The first two figures show the clusterings produced by k-means++ and Single Linkage for k = 10. We see that k-means++ finds most clusters but due to its limitation to spherical clusters, some clusters are split up and others are merged (Fig. 4a ). Single Linkage on the other hand is too much affected by the outliers: It merges most points into two clusters, using the remaining 8 clusters for very few outlier points (see Fig. 4b ). But when allowed many more clusters (here, 85 instead of 10), Single Linkage is very successful at finding the most important groups of points that belong together (see Fig. 8c in the suppl. material). Fig. 3a shows the Pareto curve. The 16th point with a separation of 0.68 is the most successful combination with repect to all metrics. It is shown in Fig. 4c .Numerical evaluation. We compare the clusterings in the approximate Pareto set to the ground truth. For this purpose we compute the Normalized Mutual Information (NMI), Rand Index (RI), and F β -scores for β = 0.5, 1, 2. Each of these measures results in values in [0, 1], where a value of 1 is achieved when the computed clustering matches the ground truth. For every measure, we pick the clustering C * in the approximate Pareto set that has highest value with respect to this measure to demonstrate that there is a good solution on the Pareto front. The full experimental evaluation, plots of Pareto fronts, other plots and also the definition of all scores can be found in Sec. A.3 in the supplementary material. On all data sets that are not synthetic, the best result in the approximate Pareto set uses a small separation value. Therefore we conjecture that it is sufficient to use a few steps of single linkage before starting k-means++ in order to improve the quality of the solution.We use two k-center-objectives with different metrics to visualize two different geodetic data sets. The goal in both cases is to visualize data, but to also make it more compact and therefore easier to understand by trying to find geographically close areas that contain similar data. Details of this section are in Supplementary Sections C.2 and C.3. The first data set we use are the monthly median incomes of the 400 districts in Germany as obtained from [29] . We compute an approximate Pareto set for k = 16 (the number of states in Germany), which contains a total of 38 different clusterings.Figure 3b shows the approximate Pareto curve. In Figure 5 one can see the 10-th Pareto-optimal solution compared to the clusterings that consider only one of the objectives. One can see that the Pareto solution has a cleaner structure than the purely income based clustering, but at the same time shows how the median income behaves in different regions of Germany.For our second application we use a data set that consists of (normalized) time series of the sea level height on different locations all over the world. We use time series that were created using the sea level simulation provided by ORA5 [18] , at the location where the tide gauge stations of the PSMSL [50, 39] are located. As metric d 1 we use the mean difference between the time series. As geographic distance measure d 2 we use the Euclidean distance between two stations. The time-series-based distance and the Euclidean distance of the gauge stations can behave very differently. We cluster with k = 150. Then the approximate Pareto set contains 106 clusterings. Table 6 shows the maximum and mean radii of the clusters in the solutions computed purely based on geometry, in the solution purely based on the time-series-based distance, and in a carefully picked Pareto-optimal solution. The numbers show that the Pareto-optimal solution is a very reasonable trade-off.A Theoretical Part: Pareto Sets for Combinations Involving k-separation Given a set of points P, k ∈ N and metrics d 1 , d 2 on P, in the previous sections we define a k-clustering on P as a set C of k centers and an assignment σ : P → C. For combinations involving k-separation, it can be helpful to view clusterings as partitionings. We introduce the following equivalent notation that is used in Sections A.1, A.2.1 and Section A.2.2.Observe that {σ -1 (c) | c ∈ C} forms a partition of P of size k. The only change in definition is that we observe that this partition is already sufficient to compute the objective values of the solution. Let C be a partition of P of size k, for i = 1, 2 we definesep(C , d i ) = min C,C ′ ∈C ,C̸ =C ′ min p∈C,q∈C ′ d i (p, q) diam(C , d i ) = max C∈C max p,q∈C d i (p, q) rad(C , d i ) = max C∈C min c∈C max p∈C d i (p, c).For convenience we view a k-clustering as a partition of P in k clusters in Sections A.1, A.2.1 and Section A.2.2.We consider the k-separation problem and observe that defining a threshold for the separation translates into a set of must-link constraints. We define the graph of points that have to be connected given a certain separation value τ and use this to define a clustering. Definition 2. Let (P, d) be a finite metric space and τ ≥ 0. The τ -separation graph G (P,d) (τ ) of P consists of• vertices V (P,d) (τ ) = P and• edges E (P,d) (τ ) = {{x, y} | x, y ∈ P : 0 < d(x, y) ≤ τ }.We denote by S (P,d) (τ ) the clustering consisting of the connected components of G (P,d) (τ ).The following shows that S (P,d) is in some sense at the heart of τ -separability. For brevity, we use the following in this lemma: We name a clusteringC of P is τ -separated if τ ≤ max C,C ′ ∈C ,C̸ =C ′ min (c,c ′ )∈C×C ′ d(c, c ′ ).Lemma 3. Let (P, d) be a metric space and τ ≥ 0. Then1. S (P,d) (τ ) is τ -separated. 2. If C is clustering of (P, d) then it is τ -separated if and only if S (P,d) (τ ) is a refinement of clustering C. This means that for every S ∈ S (P,d) (τ ) there exists someC ∈ C such that S ⊆ C.In this sense, S (P,d) (τ ) can be called the minimally τ -separated clustering.Proof. This immediately follows from two easy observations:1. The minimal distance between two different clusters S, S ′ ∈ S (P,d) (τ ) is strictly more than τ . Otherwise an edge would have been added between the respective points.2. We cannot split any cluster S ∈ S (P,d) (τ ) without lowering to separability to at most τ : since S is connected in G (P,d) (τ ) at least one edge would have to be cut.Lemma 4. Let (P, d) be a metric space consisting of n elements, and τ ≥ 0. We can computeS (P,d) (τ ) in O(n 2 ) time.Proof. The τ -separation graph can be computed in O(n 2 ) time. Connected components can be found in linear time.Now we can conclude that we can compute the optimal Pareto set (in time O(n 2 )) when we combine f 1 = sep and f 2 = sep on possibly different metrics d 1 and d 2 . Given two thresholds τ 1 and τ 2 , just compute S = S (P,d1) (τ 1 ) and merge all of its clusters S, S ′ whose distance min (s,s′ )∈S×S ′ d 2 (s, s ′ ) is at most τ 2 .In other words, we merge S and S ′ , whenever there exists a cluster S ′′ ∈ S (P,d2) (τ 2 ) with S ∩ S ′′ ̸ = ∅ and S ′ ∩ S ′′ ̸ = ∅. The resulting clustering C is minimally hierarchically compatible with both S (P,d1) (τ 1 ) and S (P,d2) (τ 2 ) in the sense that every other clustering hierarchically compatible with the latter has to be compatible with C as well. All merges we have conducted were necessarily forced to achieve the separation values. Had we left out any of them, one of the separation values would be violated. We can thus conclude with the following result. In this section, we combine k-diameter/k-center with k-separation. Although similar at first sight to the cases already discussed with k-diameter/k-center, the combinations with k-separations differ conceptually quite a bit. Whereas all prior combinations consisted of objective functions that penalize the same behavior, k-separation is concerned with a different clustering aspect. Not only do we want dissimilar points to belong to different clusters, but also for similar points to belong to the same cluster. Ideally, clusters should not only be small, but clear lines of demarcation should also run between them.Between these two goals, there is an inherent tension that cannot readily be resolved. One favors clusterings comprising a small number of clusters (at the limit there are one, or rather, two clusters), while the other favors clusterings comprising a large number of clusters (at the limit every point belongs to a separate cluster). In fact, if we fix the number of clusters, then there's no guarantee that a solution that yields constant-factor approximation for both objectives at the same time even exists, not even when the underlying metric space derives from the Euclidean line R.Next we present an example where there exists no solution that is simultaneously a constant factor approximation for k-center/k-diameter and k-separation. Example 6. For any fixed m ∈ N ≥1 consider the setP m = {1, . . . , k -1} ∪ {-x/m | x ∈ {0, . . . , m(k -1) 2 }} Am and the Euclidean metric d 1 (x, y) = d 2 (x, y) = |x -y| on R.We first show that any constant-factor approximation for either the k-diameter or the k-separation objective performs poorly for the other objective.First, note that C = {{1}, . . . , {k -1}, A m } is the only clustering with a separation value of sep(C , d 2 ) = 1. Indeed, any other k-clustering C ′ has to break up A m and so has a separation of only sep(C ′ , d 2 ) = 1/m (the distance between any two consecutive points in A m ). In other words, C is the only solution that provides a constant-factor approximation for the k-separation objective. However, C does not provide a good approximation for the k-diameter objective. Since it does not break up A m , it has a diameter of (k -1) 2 . This is worse by a factor of k -1 than just indifferently dividing up P m into k sets of "equal size". Indeed, partitioning[-(k -1) 2 , k -1] ⊃ P m into k intervals of equal length yields a clustering of diameter at most (k -1) 2 + (k -1) k = k(k -1) k = k -1.The same argument also shows that constant-factor approximations for the k-diameter objective perform poorly with respect to the k-separation objective. A solution that provides a constant-factor approximation for the k-diameter objective has to break up A m and thus has a separation value that is m times worse than the optimal.For k-center the argument works analogously with the only difference that the radius of C is lower bounded by (k-1) 2 2 while the optimal solution with respect to k-center has radius at most k-1 2 + 1.Thus, instead of trying to optimize k-diameter/k-center and k-separation simultaneously, we again focus on Pareto sets.In line with previous sections we will provide a subroutine that, given an estimation of the value of a Pareto-optimal solution, will compute a close approximation. Algorithm 1 is a relatively simple subroutine that, for a pair of possible diameter and separation values, either constructs a (1, 2)-approximation in polynomial time, or signals that no such Pareto-optimal solution exists. Using this subroutine we can simply iterate over all diameter-separation pairs and collect the results to get an approximate Pareto set P α with α = (1, 2).Algorithm 1: Approximate solution for k-diameter and k-separation input :A finite set P, two metricsd 1 , d 2 on P, a number k ∈ N, two values D, S ∈ R ≥0 . C ← {{x} | x ∈ P} while ∃C, C ′ ∈ C , C ̸ = C ′ : d 2 (C, C ′ ) < S do C ← (C \ {C, C ′ }) ∪ {C ∪ C ′ } if D < diam(C , d 1 ) or |C | < k then return no such clustering exists G ≤D ← (C , {{C, C ′ } | diam(C ∪ C ′ , d 1 ) ≤ D}) I = {I 1 , . . . , I ℓ } ← maximal independent set in G ≤D if ℓ > k thenreturn no such clustering exists partition G ≤D into star-graphs S 1 , . . . S ℓ centered around I 1 , . . . I ℓ forall i ∈ {1, . . . , ℓ} doD = ∅ forall C ∈ S i do if |C | = k then 15 return C C ← (C \ {D}) ∪ {D ∪ C} D ← D ∪ C return CBefore proving Theorem 7 we will quickly outline Algorithm 1, splitting it into two phases. In the first phase (we could also call it the Single-Linkage phase), starting with |P| clusters of size one each, we successively merge those that have a distance of less than S with regard to d 2 . This is necessary to ensure a good separation value. In the second phase (we could call this the Hochbaum-Shmoys phase) we then reduce the number of clusters further, while ensuring that the diameter with regards to d 1 does not grow too large. Consider the first case where Algorithm 1 reaches line 5. In lines 1 to 3 we have, starting with a separate cluster for each point, merged all clusters that are at a distance of at most S from each other.(Apart from the order in which the clusters get merged, this is the same as running the Single Linkage algorithm on (P, d 2 ).) Note, that a clustering in which any one such merge has not been carried out has to have a separation value strictly less than S, because there would exist two points x, y ∈ P, contained in different clusters, with d 2 (x, y) < S. In other words, to ensure a separation value of at least S, every merge performed so far has been obligatory and so, if we reach line 5, we know that C * cannot exist.Next, consider the other case in which Algorithm 1 reaches line 9. Within the second phase, we are trying to reduce the number of clusters, while maintaining a small diameter. To achieve this we have constructed a graph G ≤D in lines 6 to 7 whose edges indicate viable and cheap merges. That is, edges in this graph represent the only merges that could in fact be made without violating the requirements imposed on C * . They represent the only merges whose resulting clusters have a diameter of at most D. Now, once we reach line 9, we know that this graph contains an independent set I of size ℓ > k.As outlined above, all merges so far have been obligatory and so it follows that for each C ∈ I there exists some C * ∈ C * with C ⊆ C * . Therefore, by the pigeonhole principle there has to be a cluster C * that contains two different clusters from I . But I is an independent set in G ≤D and so diam(C * , d 1 ) ≥ diam(C * , d 1 ) > D. Again C * with the desired properties does not exist. This concludes the first part of the proof.What's left to show is that, whenever Algorithm 1 returns a clustering, it in fact returns a good clustering. In the first phase we have constructed a clusteringC * with sep(C * , d 2 ) ≥ S and diam(C * , d 1 ) ≤ D, but potentially |C * | > k.By subsequently merging clusters within star-graphs induced by an independent set within G ≤D , we are able to resolve this problem. Of course, none of the merges can decrease the separation factor, so we only have to consider how the diameter changes. This, however, is just a straight-forward application of the triangle inequality: every star-graph clearly has a diameter of at most 2D.Corollary 8. Given a finite set P and metrics d 1 , d 2 on P. We can compute the approximate Pareto set P α for α = (1, 2) with respect to the objectives f 1 = sep and f 2 = diam in polynomial time.Running Algorithm 1 with a separation value of S = 0 (or S < min{d 2 (x, y) | x ̸ = y ∈ P}) amounts to finding a 2-approximate solution for the standard k-diameter problem. Since it is known that there does not exist a polynomial-time (2 -ε)-approximation algorithm for this problem, unless P = NP [25] , we know that the (1, 2)-factor established in Theorem 7 cannot be improved.We can also combine the k-separation objective function with the k-center objective function. Since the latter is closely related to the k-diameter objective function, most analyses here will be similar to those of the previous section. We focus mostly on the subroutine because that is the only part that qualitatively changes. Phase 2 of Algorithm 1 has to be adjusted to ensure that the following theorem, analogous to Theorem 7, holds. Algorithm 2 shows the modified subroutine. The construction of our merging graph in the second phase now depends on the optimal centers of the previously computed clusters.Proof of Theorem 9. Again, we start the proof by analyzing the points of failure and show that the existence of a solution C * satisfying the bounds in the theorem leads to a contradiction. The first case, where Algorithm 2 return an error message at line 5 can be handled in exactly the same way as in the original proof and so we won't repeat it here. Instead, consider the case, where Algorithm 2 returns an error message in line 9. As before, all merges up to this point had been obligatory. Leaving out any such merge would yield a clustering that does not satisfy the lower bound for the separation. We thus know that the clustering C is in fact just a refinement of the clustering C * , which means that there have to exist two clusters C, C ′ ∈ I that are both subsets of the same clusterC * ∈ C * . But then C * has to have a radius of rad(C * , d 1 ) ≥ 1 2 diam(C ∪ C ′ ) > R, contradicting our assumptions.Algorithm 2: Approximate solution for k-center and k-separation input :A finite set P, two metricsd 1 , d 2 on P, a number k ∈ N, two values R, S ∈ R ≥0 . C ← {{x} | x ∈ P} while ∃C, C ′ ∈ C , C ̸ = C ′ : d 2 (C, C ′ ) < S do C ← (C \ {C, C ′ }) ∪ {C ∪ C ′ } if R < rad(C , d 1 ) or |C | < k then return no such clustering exists G ≤2R ← (C , {{C, C ′ } | diam(C ∪ C ′ , d 1 ) ≤ 2R}) I = {I 1 , . . . , I ℓ } ← maximal independent set in G ≤2R if ℓ > k then return no such clustering exists partition G ≤2R into star-graphs S 1 , . . . S ℓ centered around I 1 , . . . I ℓ forall i ∈ {1, . . . , ℓ} do D = ∅ forall C ∈ S i do if |C | = k then 15 return C C ← (C \ {D}) ∪ {D ∪ C} D ← D ∪ C return CFinally, we prove that any clustering returned by the algorithm is in fact a good solution. That the lower bound for the separation value is satisfied is, again, obvious. Let us thus move on to the the upper bound on the radius. After the first phase all clusters necessarily have a radius of at most R (otherwise the algorithm would fail in line 5). To see that the second phase does not increase the radius by much, fix z I ∈ I for every cluster I ∈ I . For every I ∈ I all other clusters C belonging to the star graph S of I are close to I in the sense that diam(I ∪ C) ≤ 2R. In particular d 1 (z I , x) ≤ 2R for all x ∈ C, implying that, indeed, rad( C∈S C) ≤ 2R.Corollary 10. Given a finite set P and metrics d 1 , d 2 on P. We can compute the approximate Pareto set P α for α = (1, 2) with respect to the objectives f 1 = sep and f 2 = rad in polynomial time.Again, the (1, 2)-approximation factor cannot be improved. For S = 0, Algorithm 2 computes 2approximate solutions for k-center, which is the lowest approximation ratio achievable in polynomial time [38] , unless P = NP.The instance outlined in Example 6 can again be used to show that there is no hope of finding a clustering that performs well with regard to both the k-median (or k-means) and the k-separation objective.Observation 11. Consider a set of points {x/m | x ∈ {0, . . . , mℓ}} for any ℓ and even m. The 1-median cost of this set is given bymℓ x=0 x m - ℓ 2 = 2 mℓ 2 -1 x=0 ℓ 2 - x m = 2 m mℓ 2 -1 x=0 mℓ 2 -x = 2 m mℓ 2 x=1 x = 1 4 ℓ(mℓ + 2)since the points are evenly spaced and thus the optimal center is ℓ/2. Now, if we consider the same setP k,m = {-x/m | x ∈ {0, . . . , m(k -1) 2 }} A k,m ∪{1, . . . , k -1}as in Example 6, then we run into the same issues. By the above computation, A k,m has a 1-median cost that is in Ω(k 4 ), whereas the subsets that we get from dividing [-(k -1) 2 , k -1] into k intervals of equal length each have a 1-median cost that is in O(k 2 ). The k-median cost of the only clustering C = {{1}, . . . , {k -1}, A k,m } that achieves a constant-factor approximation ratio with regard to sep is worse by a factor of Ω(k) than that of the optimum. Conversely, if we split up A k,m to achieve a good k-median solution, then the separation value will be bad.Thus, as before, we have shown that all clusterings can have a good (i.e. constant-factor) approximation ratio either with regard to the k-median objective or with regard to the k-separation objective, but not both simultaneously.Similar to the case of the k-center objective the value of the k-separation function is determined by two of the points in P, we know that for the same reasons the Pareto set for this combination consists of at most n(n-1) 2 different solutions.Theorem 12. Given a finite set P, two metrics d 1 , d 2 and objectives f 1 = sep and f 2 = med.Then we can compute the α-approximate Pareto set P α for α = (1, 2 + δ) with respect to f 1 , f 2 in polynomial time, where δ is the best approximation bound achievable for the k-median problem.The following corollary follows directly from the above theorem and the fact that Cohen-Addad et al. [16] presented a (2.67059 + ϵ)-approximation algorithm for the k-median problem.Corollary 13. We can compute the approximate Pareto set P α for α = (1, 4.67059 + ϵ) with respect to the objectives f 1 = sep and f 2 = med in polynomial time.In order to prove the theorem, we use the nesting-technique introduced for hierarchical clustering by Lin et al. [46] .Definition 14 (adapted from [46] ). We say that a clustering objective f 1 ∈ {med, mean} admits the (γ, δ)-nesting property if the following holds for every clustering instance. Let P be a finite set of points, d a metric on P and k ∈ N. We call ( C, σ) a (γ, δ)-nesting with respect to solutions (C, σ) and (C ′ , σ ′ ).The first property guarantees that points which are contained in the same cluster in (C ′ , σ ′ ) stay in the same cluster in ( C, σ) and the second property guarantees that the cost of ( C, σ) can be bounded in terms of the cost of the other two solutions. Lin et al. [46] show that k-median admits the (2, 1)-nesting property. For k-means in the Euclidean space Großwendt [7] shows that k-means admits the (4, 2)-nesting property.For k-median we follow the approach for the (2, 1)-nesting by Lin et al. [46] to compute the approximate Pareto set P (1,2+δ) with respect to f 1 = sep and f 2 = med.). The k-median objective admits the (2, 1)-nesting property. We now construct our solution by setting C = C. For p ∈ P we define the assignment as followsσ(p) = argmin c∈ C d(c, σ ′ (p)).Now notice that ( C, σ) satisfies | C| = k. Furthermore we have for points p, q ∈ P with σ ′ (p) = σ ′ (q) that σ(p) = σ(q).To bound the k-median cost, we first bound the distance of each point p to its center:d(p, σ(p)) ≤ d(p, σ ′ (p)) + d(σ ′ (p), σ(p)) ≤ d(p, σ ′ (p)) + d(σ ′ (p), p) + d(p, σ(p)) ≤ 2 • d(p, σ ′ (p)) + d(p, σ(p))The first inequality holds due to the triangle inequality. The second inequality holds due tod(σ ′ (p), σ(p)) = min c∈ C d(σ ′ (p), c) ≤ d(σ ′ (p), σ(p)) ≤ d(σ ′ (p), p) + d(p, σ(p)).Taking the sum over all points gives us:p∈P d(p, σ(p)) ≤ p∈P (2 • d(p, σ ′ (p)) + d(p, σ(p))) = 2 • med(C ′ , σ ′ , d) + med(C, σ, d).This concludes the proof.We Proof. Since we have given the minimal distance between clusters D, we know that all points that have distance smaller than D to each other must lie in the same cluster of (C * , σ * ). Therefore we can construct a clustering (C S , σ S ) that greedily clusters all of these points together.Note that if there exists a solution that fulfills our distance requirement then |C S | ≥ k since all of these groups would have to be present in (C * , σ * ) which is a k-clustering. If not, then D is chosen too large.If |C S | = k, then it must hold that (C S , σ S ) = (C * , σ * ) and we are done. Therefore we assume for the rest of the proof that |C S | > k.It is clear that all points that are clustered together in (C S , σ S ) must be clustered together in our solution (C, σ), because if there are points p, q with σ S (p) = σ S (q) but σ(p) ̸ = σ(q) we have d 1 (p, q) < D and therefore sep(C, σ) < D. Therefore the solution (C, σ) must be compatible with (C S , σ S ) and at the same time ensure that the k-median cost with respect to d 2 is not too high. To ensure this, we denote by (C M , σ M ) a δ-approximation to the best k-median solution (w.r.t.d 2 ). Therefore (C M , σ M ) is also a δ-approximation to (C * , σ * ).Since the separation cost function is independent of the set of centers C S we can without loss of generality choose the center set to be the set of points that minimizes med(C S , σ S , d 2 ). Since points which are in the same cluster in (C S , σ S ) have to be in the same cluster in (C * , σ * ) as well, we knowEQUATIONNow let (C, σ) be a clustering which is a (2, 1)-nesting with respect to (C M , σ M ) and (C S , σ S ). Such a clustering exists by Lemma 15.For all p, q with d 1 (p, q) < D it holds that σ S (p) = σ S (q) and therefore also σ(p) = σ(q). Thus we obtain sep(C, σ, d 1 ) ≥ D. For the k-median cost with respect to d 2 we obtainmed(C, σ, d 2 ) ≤ 2 • med(C S , σ S , d 2 ) + med(C M , σ M , d 2 ) ≤ 2 • med(C * , σ * , d 2 ) + δ • med(C * , σ * , d 2 ) = (2 + δ) • med(C * , σ * , d 2 ),where the last inequality holds because of inequality (1) . This concludes the proof.The theorem now follows from the fact that there are only n(n-1) 2 many possible values for D and we can test all of them in polynomial time. Note that in the last steps of the proof of Lemma 16 we saymed(C M , σ M , d 2 ) ≤ δ • med(C * , σ * , d 2 ). The same guarantee holds also with the optimal k-median clustering instead of the Pareto-optimal solution (C * , σ * ), and in cases where the Pareto-optimal solution has bad values for the k-median target function, this might be a big advantage.The combination of k-separation and k-means works exactly the same way, with the exception that we cannot simply use the triangle inequality in the analysis, leading to the following theorem. The following corollary follows directly from the above theorem and the fact that Ahmadian et al. [4] presented a (9 + ϵ)-approximation algorithm for the k-means problem in general metrics.Corollary 18. We can compute the approximate Pareto set P α for α = (1, 25 + ϵ) with respect to the objectives f 1 = sep and f 2 = mean in polynomial time.We now follow the approach that Lin et al. [46] used to get a (8, 2)-nesting, but without setting τ = 2 at the end of the proof, which leads to the following more general statement: Lemma 19 ( [46] ). The k-means objective admits the (4 + τ 2 , 1 + 4 τ 2 )-nesting property for all τ > 0.Proof. Analogously to the proof of Lemma 15 we get:d(p, σ(p)) 2 ≤ (2 • d(p, σ ′ (p)) + d(p, σ(p))) 2 = 4 • d(p, σ ′ (p)) 2 + 4 • d(p, σ ′ (p))d(p, σ(p)) + d(p, σ(p)) 2 ≤ (4 + τ 2 ) • d(p, σ ′ (p)) 2 + (1 + 4 τ 2 ) • d(p, σ(p)) 2for all τ > 0. The last inequality follows from the fact that 4ab ≤ τ 2 • a 2 + 4 τ 2 • b 2 for all a, b, τ > 0. Summing up over all points leads to:p∈P d(p, σ(p)) 2 ≤ p∈P (4 + τ 2 ) • d(p, σ ′ (p)) 2 + (1 + 4 τ 2 ) • d(p, σ(p)) 2 = (4 + τ 2 ) • mean(C ′ , σ ′ , d) + (1 + 4 τ 2 ) • mean(C, σ, d).In the following lemma, we can now choose the value of τ in relation to the available k-means approximation factor δ in order to improve our approximation factor. For all p, q with d 1 (p, q) < D it holds that σ S (p) = σ S (q) and therefore also σ(p) = σ(q). Thus we obtain sep(C, σ, d 1 ) ≥ D.For the k-means cost with respect to d 2 we obtainmean(C, σ, d 2 ) ≤ (4 + 2 √ δ) • mean(C S , σ S , d 2 ) + (1 + 2 √ δ ) • mean(C M , σ M , d 2 ) ≤ (4 + 2 √ δ) • mean(C * , σ * , d 2 ) + δ(1 + 2 √ δ ) • mean(C * , σ * , d 2 ) = (4 + 2 √ δ) • mean(C * , σ * , d 2 ) + (δ + 2 √ δ) • mean(C * , σ * , d 2 ) = (4 + 4 √ δ + δ) • mean(C * , σ * , d 2 ),where the last inequality holds because (C M , σ M ) is a δ-approximation to the optimal k-means solution. This concludes the proof.In this section, we combine the k-separation and the k-msr objectives. Notice that we here allow that clusterings have less than k clusters.The k-msr objective differs from other center-based objectives on a fundamental level. Whereas it is always optimal with regard to the k-center, the k-median, or the k-means objectives to assign points to their closest center, the same does not hold for the k-msr objective. Even on a line graph and even when the centers are chosen optimally, assigning points to their closest centers can result in a clustering whose k-msr cost is three times the cost of an optimal solution [45] , and for more complicated metric spaces this factor grows quickly. In particular, the black-box approach that we have used in the previous two sections is not applicable here because it relies heavily on this property. Instead, we will work through the explicit primal-dual algorithm of Buchem et al. [11] and show that it still works if we replace single points with preformed clusters. Before that, however, let us quickly ascertain, as before, that these two objectives cannot be approximated well simultaneously. Observation 21. The example that we now provide does not turn out to be as bad as the ones given in Example 6 or Example 11. This is because we can often merge clusters that are close to each other without increasing the k-msr cost by much. If we were to consider the other examples, then we would quickly find that the same arguments do not hold. For example, in the k-diameter case, we only had to compare the clustering C = {{1}, . . . , {k -1}, A k,m } with one that evenly partitions P k,m as a subset of [-(k -1) 2 , k -1] into k sets of equal length k -1, to deduce that C, which is the only constant-factor approximation with regard to the k-separation objective, is only Ω(k)-approximative with regard to the k-diameter objective. However, with regard to the k-msr objective we would have to sum up all the radii of the second partitioning and so end up with clustering whose is cost is also in the order of Ω(k 2 ). In other words, this example does not show that C is a bad clustering with regard to the k-msr objective. Instead we consider a graph metric consisting of two parts:1. a line graph consisting of k -1 points, where all edges have weight 1;2. a clique consisting of k -1 points, where all edges have weight √ k.Each distance d(x, y) on the union of both graphs is given as the weight of a shortest path between x and y. For there to always exist such a path we can just add a single edge somewhere between the first and the second part with arbitrarily large weight. Now let us consider the only constant-factor approximation with regard to the k-separation objective. As before, this clustering results from merging all points in the line graph and leaving all points in the clique separate. Its separation value is √ k, whereas every other clustering has to have a separation value of 1 because it has to split up the line graph. However, the k-msr cost of this solution is ⌈ k-1 2 ⌉, which is worse by a factor of √ k than merging the clique and leaving each point in the line graph separate, as the latter has a k-msr cost of exactly √ k.With this established, let us find a convenient formulation of the k-mim-sum-radii problem to be used in this section. We first recall the notion of balls around points. In the introduction, we said that the solution of an instance (P, d) of the k-msr problem is an assignment function σ : P → C from P to a subset C ⊂ P that consists of k centers. The stated goal was to find a σ that minimizes c∈C max x∈σ -1 (c) d(x, c). Since the cost of a single cluster is determined only by two points, we can conceptualize solutions slightly differently. Instead of an assignment we are looking for k pairs (c 1 , r 1 ), . . . , (c k , r k ) ∈ P × R that minimize i r i and that guarantee that P ⊆ i B (P,d) (c i , r i ). Each such pair induces a (not necessarily unique) assignment by mapping each point x ∈ P to a center c i with d(x, c i ) ≤ r i . We will work with this formulation in the remainder of this section. The following shows how we wish to combine the k-separation and k-msr objective functions. Definition 23 (The τ -separated k-msr problem). Let d 1 , d 2 be two metrics over a finite set P, k ∈ N, and τ ≥ 0. The goal in the τ -separated k-msr problem is to find k pairs P = {(c 1 , r 1 ), . . . , (c k , r k )} that minimize cost(P ) = k i=1 r i and that guarantee that for all S ∈ S (P,d1) (τ ) there exists some i S ∈ {1, . . . , k} with S ⊆ B (P,d2) (c i S , r i S ).Instead of starting with individual points, we compute the minimally τ -separated clustering in a preprocessing step and then only subsequently merge clusters in this clustering to reach k clusters. By slightly adjusting the approach by Buchem et al. [11] we get the following result. Theorem 24. There exists a (3 + ε)-approximation algorithm for the τ -separated k-msr problem that runs in n O(1/ε) time.The approximation factor is exactly the same as in the original paper. Before getting into the details of Buchem et al.'s primal-dual algorithm we have to note an essential observation established by Buchem et al. Definition 25. Let (P, d) be a finite metric space and Q ⊂ P × R a finite set of pairs. The intersection-graphG (P,d) (Q) of Q consists of • vertices V (P,d) (Q) = Q and • edges E (P,d) (Q) = {{(c, r), (c ′ , r ′ )} | B (P,d) (c, r) ∩ B (P,d) (c ′ , r ′ ) ̸ = ∅}.One of the most interesting properties of the k-msr objective is that the cost of a solution can sometimes be reduced by merging clusters (which cannot happen with the other center-based objectives). For example, this is the case whenever c i ∈ B (P,d) (c j , r j ), i.e., when the center of one pair is contained within the ball of another pair. The following result of Buchem et al. shows that we can merge sets of intersecting clusters without introducing too much additional cost. Lemma 26 (Cf. Appendix C of [11] ). Let (P, d) be a finite metric space, Q ⊆ P × R a finite set of pairs whose intersection-graph G (P,d) (Q) is connected, and I ⊂ V (P,d) (Q) an independent set that maximizes (c,r)∈I r. Then there exists a pair (c * , r * ) ∈ P × d(P × P) such that1. (c,r)∈Q B (P,d) (c, r) ⊂ B (P,d) (c * , r * ) and 2. r * ≤ 3 (c,r)∈I r.The proof of this result is dispersed over several technical results contained in Appendix C of [11] . Since it does not concern our new constraints, we won't repeat it here. However, with this taken care of, we are now in the position to work through the actual primal-dual algorithm. Fix an arbitrary instance (a finite set P, two metrics d 1 and d 2 over P, a number k ∈ N, a threshold τ ≥ 0) and let (c * 1 , r * 1 ), . . . , (c * k , r * k ) denote the pairs of optimal solution P for the τ -separated k-msr problem in non-increasing order of their radii. The first step is common to all primal-dual approaches for the k-msr problem ( [13, 28, 11] ) and consists of guessing the 1/ε largest pairs (c * 1 , r * 1 ), . . . , (c * 1/ε , r * 1/ε ) of the optimal solution (where we assume w.l.o.g. that 1/ε ∈ N). This can be done in n O(1/ε) time and leaves us to only have to approximate the remainingk ′ = k -1/ε pairs (c * 1/ε , r * 1/ε ), . . . , (c * k , r * k ).The pairs comprising the optimal solution can be of drastically different size, but this segmentation ensures that all leftover clusters S ′ = {S ∈ S (P,d1) (τ ) | ∀i ∈ {1, . . . , 1/ε} : S ̸ ⊆ B (P,d2) (c i , r i )} can be covered by balls of radii at most r 1/ε ≤ ε • cost(P). This will give us some breathing room later on. From now on we can focus on the τ -separated k ′ -msr problem for P ′ = S∈S ′ S.For the second step of the algorithm, let us set up the primal and dual LP corresponding to the problem. While they look quite similar to those for the vanilla k-msr problem, conceptually they are slightly different. While Buchem et al. only have to cover individual points, we have to ensure that clusters from S ′ = {S 1 , . . . , S ℓ } are always covered as a whole.Primal LP:minimize (c,r) r • x (c,r) subject to (c,r):Sj ⊂B (P,d 2 ) (c, r) x (c,r) ≥ 1 ∀j ∈ {1, . . . , ℓ} (c,r) x (c,r) ≤ k ′ x (c,r) ≥ 0where we have a variable x (c,r) for every pair (c, r) consisting of a center c ∈ P and a radius r ∈ R := {d(x, y) | x, y ∈ P : d(x, y) ≤ r * 1/ε }. The corresponding dual LP is as follows:Dual LP: maximize j α j -λk ′ subject to j : Sj ⊂B (P,d 2 ) (c, r) α j ≤ r + λ ∀(c, r) α j ≥ 0 ∀j ∈ {1, . . . , ℓ} λ ≥ 0As expected, the second step consists of computing a solution for the dual LP that can almost fully pay for a solution of the original τ -separated k-msr problem. While this is the standard for primal-dual algorithms, Buchem et al.'s specific approach for the vanilla versions differs significantly from the earlier approaches of both Charikar and Panigrahy [13] , as well as Friggstad and Jamshidian [28] . α j ≥ r + λ -µ.Starting with the trivial solution α 1 = . . . = α ℓ = 0 and λ = 0, Buchem et al. successively increase the values in such a way that the number of connected components of the intersection-graph of almost tight pairs decreases while still guaranteeing that the solution stays valid and that every point is contained in the ball of at least one almost tight pair. Roughly speaking, once they reach k ′ connected components, they're able to derive a good solution for the k ′ -msr problem on P ′ with the help of Lemma 26.The overall approach is the same for us, but we have to modify the invariant to ensure that the clusters S ∈ S ′ are fully contained within the ball of at least one tight pair. Now, contrary to the vanilla case, in which the trivial solution satisfies the invariant, because which every point x ∈ P ′ is contained within the respective ball B (P,d2) (x, 0), the trivial solution for our LP does not necessarily satisfy our modified invariant. This is because the balls of radius 0 do not necessarily cover all clusters S ∈ S ′ . But this can easily be rectified by successively increasing the α j 's for clusters S j that are not yet covered at a uniform speed and end when no such cluster remains. At the end of this phase, the invariant will be satisfied and we can continue in the same manner as Buchem et al. Let T denote the set of currently tight pairs. Since no α j can be increased on its own, from now on we also have to increase λ to offset this. Even then, if there is an (almost) tight pair, whose ball covers two different clusters from S ′ , then we cannot increase both of them, as this would (quickly) lead to a violation of the respective constraint. Like Buchem et al. we greedily choose a maximal set of α j 's in such a way that no two corresponding clusters are fully contained within the ball of some pair from T . These variables as well as λ are increased uniformly by some value until one additional pair that until then wasn't almost tight becomes tight. Due to the choice of the α j 's, the validity of the solution is guaranteed and the invariant satisfied. As long as the intersection-graph of the updated set T contains strictly more than k ′ connected components, we will increase the α j values of at least k ′ + 1 clusters, which means that the objective value of the solution increases as well. By relating this increase in cost during each iteration to the upper bound k ′ r * 1/ε of the primal LP, Buchem et al. prove that the number of possible iterations is upper bounded by O |P| 4 (or rather O k|P| 3 ). In particular, this shows that the process can be continued until at most k ′ connected components are left.From this point onward, the remaining analysis is independent of the newly imposed constraints and so we will not cover it in detail. Just note that the resulting set of almost tight clusters T satisfies all the requirements that are necessary for us to conclude the proof in the same manner as Buchem We will calculate a (2, 2)-approximate Pareto set for the combination of two objectives f 1 , f 2 ∈ {diam, rad}. To do this we adapt the algorithm by Hochbaum and Shmoys [37] , which computes a 2-approximation for the objectives rad, diam, to the case where we want to optimize over two such objectives simultaneously.Remember that we are given two metrics d 1 , d 2 on P and want to minimize f i with respect tod i . Let R = R 1 × R 2 , where R i = {d i (v, w) | v, w ∈ P}.For any pair of distances (R 1 , R 2 ) let G R1,R2 denote the graph containing an edge between exactly those pairs of nodes v, w ∈ P fulfilling that d 1 (v, w) ≤ R 1 and d 2 (v, w) ≤ R 2 . We adjust the algorithm by Hochbaum and Shmoys [37] as follows. Let β i = 1 if f i = diam and β i = 2 if f i = rad throughout the remainder of this section. As in the original algorithm we can use the graph G β1R1,β2R2 to test for a pair of distances (R 1 , R 2 ) ∈ R whether there exists a solution with cost (2R 1 , 2R 2 ) or decide that there is no solution with cost (R 1 , R 2 ). Lemma 29. If the graph G β1R1,β2R2 contains an independent set of size greater than k then there does not exist a solution with cost at most (R 1 , R 2 ).Proof. Let us assume that there exists a solution (C, σ) Proof. For every node v we can simply set σ(v) = v if v ∈ I or σ(v) = c for a neighbor c of v in I (there always exists such a neighbor because otherwise I would not be maximal). If f i = rad it holds that d i (p, σ(p)) ≤ 2R i and thus rad(I, σ, d i ) ≤ 2R i . If f i = diam it holds for p, q ∈ P with σ(p) = σ(q) that d i (p, q) ≤ 2R i and thus diam(I, σ, d i ) ≤ 2R i .with cost (R 1 , R 2 ). Let v, w ∈ P with σ(v) = σ(w). Observe that d i (v, w) ≤ 2R i if f i = rad and d i (v, w) ≤ R i if f i = diami be defined as the biggest distance with respect to d i smaller or equal than β i R i between a pair of points in P. Observe that actuallyG β1R1,β2R2 = G R ′ 1 ,R ′ 2 .Thus we obtain the following corollary of Lemma 29.Corollary 31. Let R ′ i = max p,q∈P:di(p,q)≤βiRi d i (p, q) for i = 1, 2. If G R ′ 1 ,R ′2 contains an independent set of size greater k then there exists no solution with cost at most (R 1 , R 2 ).In conclusion it is sufficient to compute a maximal independent set in G R1,R2 for all (R 1 , R 2 ) ∈ R = R 1 × R 2 (remember that values in R directly correspond to potential cost values). If the independent set has size less or equal to k we include the respective solution in the approximate Pareto set. Because of Lemma 30 and Corollary 31 one obtains a (2, 2)-approximate Pareto set. Given that R i contains O(n 2 ) distances between points in P and the calculation of a maximal independent set in O(n 2 ) we can compute the approximate Pareto set in time O(n 6 ). One can easily improve upon the running time by observing the following. If we find an independent set of size greater k in the graph G R1,R2 we do not have to consider any combination (R ′ 1 , R 2 ) with R ′ 1 < R 1 . Similarly if the maximal independent set has size at most k one does not need to consider any combination (R 1 , R ′2 ) with R ′ 2 > R 2 since it would be dominated by the currently found solution anyway. We combine both observations to reduce the number distances in R which we have to consider.We start with the largest distance R 1 ∈ R 1 and the smallest distance R 2 ∈ R 2 and increase the R 2 if the maximal independent set computed in G R1,R2 has size > k, we decrease R 1 otherwise. This way one would still obtain a (2, 2)-approximate Pareto set while reducing the number of considered pairs in R from O(n 4 ) to O(n 2 ) which yields a total running time of O(n 4 ).This can be further improved by observing the following. If we already have calculated the graph G R1,R2 and a maximal independent set in this graph we probably do not need to recalculate the entire graph and independent set if we slightly decrease R 1 (and thus remove edges from the graph) or slightly increase R 2 (which adds edges). Instead one can simply modify the current graph while keeping track how this affects the independent set. This is far cheaper most of the time. To update the independent set properly we store for each node p ∈ P the set B p of its neighbors contained in the current independent set (intuitively these are the nodes that keep p from joining the independent set as well). Following this idea one ends up with Algorithm 3. In the following we will prove its correctness and that its running time is O(n 3 ).sort distances d 1 (p, q) for p, q ∈ P:d (1) 1 ≤ . . . ≤ d (m) 1sort distances d 2 (p, q) for p, q ∈ P: d foreach point pair p, q with d 1 (p, q) = R 1 and d 2 (p, q) ≤ R 2 do REMOVEEDGE({p, q}) R 1 = d (i-1) 1 return P (2,2)Lemma 32. The following invariants are true for Algorithm 3 (at the beginning of line 6):1. (P, E) = G R1,R22. I is a maximal independent set of G R1,R23. For all p ∈ P, it holds that B p is the set of neighbors of p contained in I.The invariant can be proven via a straightforward induction. The main idea is, that if we remove an edge between a point p in the independent set I and another point q we need to check whether q has Algorithm 4: ADDEDGE({p, q}) W.l.o.g. q ∈ I ⇒ p ∈ I if p ∈ I then B q = B q ∪ {p} if p ∈ I, q ∈ I then I = I \ {q} for {q, r} ∈ E do B r = B r \ {q} if |B r | =E = E \ {{p, q}} if p ∈ I or q ∈ I then set v = p, w = q if q ∈ I, set v = q, w = p otherwise B v = B v \ {w} if |B v | = 0 then I = I ∪ {v} foreach neighbor r of v do 8 B r = B r ∪ {v}still neighbors in the independent set left (i.e. B q ̸ = ∅). If this is not the case we need to add q to the independent set to keep it maximal.If we add an edge, the only critical case appears when it connects two nodes p, q which are both in the independent set. If this is the case, we need to remove one of them from I to keep it an independent set. However if we remove q we need to check for every neighbor r if it can now be added to I (i.e., the respective set B r is empty) to ensure that I stays maximal. In both operations the entries B x are updated for all x ∈ P accordingly. Theorem 33. Algorithm 3 calculates a (2, 2)-approximate Pareto set.Proof. Let us consider an arbitrary solution S with cost R * i with respect to f i for i = 1, 2. We choose i ′ , j ′ such that d(i ′ ) 1= max p,q∈P:d1(p,q)≤β1R * 1 d 1 (p, q) and d(j ′ ) 2= max p,q∈P:d2(p,q)≤β2R * 2 d 2 (p, q). Using Corollary 31 we may conclude that if Algorithm 3 reaches an iteration with i = i ′ and j = j ′ the maximal independent set has size at most k. By Lemma 30 this results in a solution with cost(2R * 1 , 2R * 2 )which is added to P (2,2) . However there might be two cases which prevent this situation from happening:• Case 1: At some point during the execution of the algorithm i = i ′ , j ≤ j ′ and i gets decreased.One might note that i only gets decreased if an independent set of size at most k has been found inEQUATION. Since d(i ′ ) 1 ≤ β 1 R * 1 and d (j) 2 ≤ d (j ′ ) 2≤ β 2 R * 2 we obtain by Lemma 30 that a solution with cost (2R * 1 , 2R * 2 ) has been found. Thus S is (2, 2)-approximated. • Case 2: At some point during the execution of the algorithm i ≥ i ′ , j = j ′ and j gets increased.We observe that j gets only increased if the current independent set I of the algorithm has size greater k. Furthermore the edge set ofEQUATION.Thus I is also an independent set of G d(i ′ ) 1 ,d (j ′ ) 2. However by Corollary 31 this means that there cannot exist a solution with cost (R * 1 , R * 2 ) which is a contradiction.Thus we may conclude that any solution is at least (2, 2)-approximated by one of the solution contained in P (2,2) . Now we want to bound the running time of the algorithm. To do this, we will introduce a potential function Φ whose value is determined by the current state of the edge set E and the independent set I of the algorithm. We define Φ((P, E), I) = p∈I deg (p) where deg(p) is the degree of p in (P, E). Another way to think about this potential is that it is the sum of the size of B p for every node p, because each node in the independent set blocks every neighbor q from becoming part of the independent set itself and thus appears in the respective set B q . We will now bound both the cost of the operation REMOVEEDGE({p, q}), as well as those of ADDEDGE({p, q}) by a function in O(n) plus the respective potential change ∆Φ induced by this change (which might be negative).Before Proof. If neither p nor q are contained in I, the potential does not change while we only incur constant cost and the lemma holds. Otherwise let w.l.o.g. p be contained in I (note that not both nodes can be contained in I since they were connected by an edge). We distinguish two cases:If q has another neighbor in I besides p, i.e. |B q | ≥ 2, then the size of B q decreases by 1 and the potential Φ also decreases by 1. Thus O(2 + ∆Φ) = O(1) while the operation takes only constant time.If p was the only neighbor of q that was contained in the independent set, q gets added to I as well to ensure that I is maximal. As a result for every neighbor r of q we need to add q to B r which leads to a running time of O(c), where c is the number of neighbors of q, after the edge {p, q} has been removed. At the same time every neighbor of q also increases the potential Φ by one when q gets added to I. Proof. The only critical case is that both p and q are contained in I because otherwise we only incur constant cost while also the potential only changes by a constant. In this case the node q gets removed from the independent set which means that for every neighbor r we need to remove q from B r . Since q has at most n neighbors the cost of this procedure lies in O(n) while the potential decreases by at most n. However if q was the only neighbor of r within I we need to add r to I to ensure that I is maximal. As a result we again need to update the set B s for all neighbors s of r, which costs O(deg(r)) while the potential gets increased by deg(r). In total we get that the cost of ADDEDGE is bounded by O n + r∈I ′ deg(r) , where I ′ denotes the set of nodes newly added to the independent set. At the same time:O(2n + ∆Φ) = O 2n -n + r∈I ′ deg(r) = O n + r∈I ′ deg(r)Thus the lemma holds.Using these two lemmas we can now bound the running time of Algorithm 3: Theorem 36. The running time of Algorithm 3 lies within O(n 3 ).Proof. The running time of the algorithm mainly consists of three parts:• The sorting of the distances in the beginning which needs time O(n 2 log(n))• Up to n(n-1) 2 calls of DELETEEDGE and ADDEDGE each (as each point pair gets inserted and deleted at most once). Using the previous two lemmas we can bound the respective costs by O(2 + ∆Φ) and O(2n + ∆Φ). One might note that both at the beginning as well at the end of the algorithm there is not a single edge in the edge set which means that Φ = 0. Thus the total change of the potential is 0 and we can bound the total cost of the insertion and deletion operations by O(n 3 ).• Constructing a solution from the independent set costs at most O(n) since we only have to extract an element of B p for every point p ∈ P. Since at most O(n 2 ) solutions get added to P (2,2) (one for every i in line 5 of Algorithm 3) the total time for constructing the solutions lies in O(n 3 ).Thus also the entire running time is bounded by O(n 3 ).The following corollary is an immediate consequence of Theorem In this section we will prove that there can actually exist Ω(n 2 ) different Pareto optimal solutions if we combine two different k-center/k-diameter objectives with each other. Lemma 38. For every n ∈ N and f 1 , f 2 ∈ {rad, diam} there exist a set of n points P and metrics d 1 , d 2 on P such that the size of the Pareto set P with respect to f 1 , f 2 is in Ω(n 2 ).Proof. Let P be a set of size n. We chose the metrics d 1 , d 2 on P as follows. Let p 1 , ..., p m be all pairs of distinct points in P (i.e. m = n(n-1)). For every i we set d 1 (p i ) to 1 + i m and d 2 (p i ) to 2 -i m . Furthermore we set d 1 (p, p) = d 2 (p, p) = 0 for all p ∈ P. One may note that the distance between two distinct points lies always between 1 and 2. Thus the triangle inequality is trivially fulfilled and d 1 , d 2 are indeed metrics on P. Now we consider the situation were we want to compute a k-clustering with k = n -1. Observe that only a single point gets assigned to a center besides itself. Then every k-clustering corresponds to one pair p i of points that are contained in the same cluster and vice versa. The cost of this solution is (d 1 (p i ), d 2 (p i )). It is easy to observe that each of theses solutions is in fact Pareto optimal. Let p i and p j be two pairs and assume w.l.o.g that i < j. Then it holds that d 1 (p i ) < d 1 (p j ) while d 2 (p i ) > d 2 (p j ) which means that neither solution dominates the other one. Thus we end up with m ∈ Ω(n 2 ) different Pareto optimal solutions. However one might note, that in the clustering instance constructed to prove Lemma 38 many solutions differ only by a small factor. One could obtain a (2, 2)-approximate Pareto set of size 1 by just choosing an arbitrary solution. While this is of course a special case one can prove that in fact there always exists a (2, 2)-approximate Pareto set of size n. This result is a direct consequence of the fact that in a metric there can only be a limited number of distances between point pairs (which correspond to potential k-center/k-diameter solutions) that differ pairwisely by a factor of 2. Lemma 39. Let P be a set of n points and let d be a metric on P. Then there do not exist n pairs of points p 1 , ..., p n in P such that for all i ̸ = j it holds that d(p i ) ≤ 1 2 d(p j ) or d(p i ) ≥ 2d(p j ).Proof. Suppose the statement would be wrong. Then there exists a subset of indices i 1 , .., i k such that p i1 = {v i1 , w i1 }, ..., p i k = {v i k , w i k } and w ij = v ij+1 for all j = 1, . . . , k -1 and w i k = v i1 . Let w.l.o.g. the distance of p i1 be maximum among distances of all p ij . Then it holds by the triangle inequality thatd(p i1 ) ≤ k j=2 d(p ij ).We might observe that the second longest edge is at most half as long as p i1 and that the third longest edge is at most half as long as the second longest and so on. Thus we obtaind(p i1 ) ≤ d(p i1 ) k j=1 1 2 j < d(p i1 ).which is a contradiction.The following corollary is a consequence of Lemma 39.Corollary 40. Given a set P of n points, two metrics d 1 , d 2 on P, k ∈ N and two objectives f 1 , f 2 ∈ {rad, diam}. There exist a (2, 2)-approximate Pareto set with respect to f 1 , f 2 of size O(n).Proof. Let P be the Pareto set induced by f 1 , f 2 . We will now construct a (2,2)-approximate Pareto set Q of P. We will do this by iterating through P. First let Q = ∅. We start by adding the solution that optimizes f 1 to Q. Then we move along the curve by improving f 2 while getting worse in f 1 .Whenever we encounter a solution that is not (2,2)-approximated by the previous points in Q, we add it. We repeat this until we reach the end of the curve.Let x and y be two neighboring solutions in Q. Without loss of generality we assume that x was added to Q before y. Note that since we only get worse in f 1 we know that f 1 (x) < f 1 (y) and therefore it must hold that f 2 (y) < 1 2 f 2 (x) since otherwise x would (2,2)-approximate y. By construction Q is a (2,2)-approximate Pareto set to P. Now assume for contradiction that |P| > n. Then there would have been added more than n solutions to Q, such that for all x ̸ = y ∈ Q it holds that either f 2 (x) > 2f 2 (y) or f 2 (y) > 2f 2 (x). Since all solutions correspond directly to pairwise distances in d 2 of our point set P, this is a contradiction to Lemma 39 and therefore the corollary follows.We consider the combination of k-center with k-median or k-means with respect to two distinct metrics d 1 and d 2 . It is easy to see, that the size of the Pareto set is bounded by the number of possible radii for k-center. Since this is always the distance between two points, we obtain |P| ≤ n(n-1) 2 . Alamdari and Shmoys [5] show that we can compute the approximate Pareto set P α for α = (4, 8) with respect to f 1 = rad and f 2 = med and the special case where d 1 = d 2 . They modify the LP-based approach by Charikar et al. [12] for k-median to compute a solution which is also a good approximation to the radius.In a similar way we show that the approach for k-median by Jain and Vazirani [41] can be modified to compute the approximate Pareto set P α for α = (9, 6 + ϵ) in the more general case d 1 ̸ = d 2 . Theorem 41. Given a finite set P, two metrics d 1 , d 2 on P, k ∈ N. If for R > 0 there exists a solution (C, σ) for P with rad(C, σ, d 1 ) ≤ R we can compute a solution(C ′ , σ ′ ) in polynomial time such that rad(C ′ , σ ′ , d 1 ) ≤ 9 • R and med(C ′ , σ ′ , d 2 ) ≤ (6 + ϵ) • med(C, σ, d 2 ).Since the algorithm in [41] also produces a (54 + ϵ)-approximation for k-means we can also adapt it to compute the approximate Pareto set P α for α = (9, 54 + ϵ) for the case f 1 = rad and f 2 = mean. Theorem 42. Given a finite set P, two metrics d 1 , d 2 on P, k ∈ N. If for R > 0 there exists a solution (C, σ) for P with rad(C, σ, d 1 ) ≤ R we can compute a solution(C ′ , σ ′ ) in polynomial time such that rad(C ′ , σ ′ , d 1 ) ≤ 9 • R and mean(C ′ , σ ′ , d 2 ) ≤ (54 + ϵ) • mean(C, σ, d 2 ).We assume that the algorithm by Alamdari and Shmoys [5] for k-center and k-median can also be adapted to the combination of k-center and k-means with an adjusted approximation factor.For the case f 1 = rad and f 2 = med we can compute the approximate Pareto set P α for α = (9, 6+ϵ) by checking all n(n-1) 2 possible values for the radius R. Suppose there exists a k-center solution for P with radius ≤ R and let (C R , σ R ) be such a solution that minimizes the k-median cost. Theorem 41 implies that we can compute a solution(C ′ R , σ ′ R ) with f 1 (C ′ R , σ ′ R , d 1 ) ≤ 9 • R and med(C ′ R , σ ′ R , d 2 ) ≤ (6 + ϵ) • med(C R , σ R , d 2) in polynomial time. Let P α be the set containing all these solutions, then P α is an α-approximate Pareto set. Following the same approach we can compute the approximate Pareto set P α for α = (9, 54 + ϵ) in the case f 1 = rad and f 2 = mean. This yields the following corollary. To prove Theorem 41 we repeat the (6 + ϵ)-approximation algorithm for k-median proposed by Jain and Vazirani [41] and explain the relevant changes to obtain a solution which also approximates the radius. Following [41] we first develop an algorithm for the facility location problem.In the facility location problem we deal with a set F of possible facilities and a set D of clients. Furthermore we are given a metric d on F ∪ D and facility opening costs f (i) ≥ 0 for every i ∈ F . The task is to compute a set C ⊂ F which minimizes the sum of opening costs and distances between a client and its closest facility i∈C f (i) + j∈D min i∈C d(i, j). Later, when we use the algorithm for facility location to solve the k-median problem on the set P, we set F = D = P.We consider the combination of facility location with the k-center objective. Suppose we are given two metrics d 1 , d 2 on F ∪ D and want to minimize the facility location cost (with respect to d 2 ) as well as the maximum distance between a client and its facility (with respect to d 1 ). Now a client may not be assigned to its nearest facility with respect to d 2 , since this may result in a large radius with respect to d 1 . Thus we say that a solution consists of a set C ⊂ F and an assignment σ : D → C of clients to facilities. We seek to minimize the objectives rad(C, σ, d 1 ) = max j∈D d 1 (j, σ(j)) and fac(C, σ, d 2 ) = i∈C f (i) + j∈D d 2 (j, σ(j)).Theorem 45. Given a set of facilities F with opening costs f (i) ≥ 0 for i ∈ F , clients D, two metrics d 1 , d 2 on F ∪ D and a number R > 0. If there exists a solution (S, τ ) with rad(S, τ, d 1 ) ≤ R, then we can compute a solution (C, σ) in polynomial time such that rad(C, σ, d 1 ) ≤ 3 • R and3 i∈C f (i) + j∈D d 2 (j, σ(j)) ≤ 3 • fac(S, τ, d 2 ).For some radius R > 0 we want to compute an optimal facility location solution with respect to d 2 under the side constraint that the radius of every emerging cluster is at most R with respect to d 1 . We consider the standard formulation of the facility location problem as an integer program with the additional constraint that a client can only be assigned to a facility if it is at a distance at most R. Let M = {(i, j) | i ∈ F, j ∈ D, d 1 (i, j) ≤ R} be the set of all such combinations. We consider the following integer program.minimize i∈F f (i)y i + (i,j)∈M d 2 (i, j)x ij subject to (i,j)∈M x ij ≥ 1 ∀j ∈ D x ij ≤ y i ∀(i, j) ∈ M x ij ∈ {0, 1} ∀(i, j) ∈ M y i ∈ {0, 1} ∀i ∈ FGiven an optimal solution (x, y) of this program we open a facility i ∈ F iff y i = 1 and assign a client j to i iff x ij = 1. Let (C, σ) be the respective solution for facility location. It is easy to see that we have rad(C, σ, d 1 ) ≤ R since we only allow a client to be assigned to a facility within distance of R with respect to d 1 .To obtain the linear program we relax the last constraints to x ij ≥ 0 and y i ≥ 0. Its dual is then given by maximize j∈Dα j subject to α j -β ij ≤ d 2 (i, j) ∀(i, j) ∈ M (i,j)∈M β ij ≤ f i ∀i ∈ F α j ≥ 0 ∀j ∈ D β ij ≥ 0 ∀(i, j) ∈ MWe construct a solution for the dual LP by starting with α j = 0 for all j ∈ D and growing them simultaneously at the same rate until some stopping condition is met. Later on the variable α j will pay for the connection cost of client j and it will pay partially for the opening cost of some facility.As in the algorithm in [41] we introduce the notion of time. We start at time 0, where all variables are set to 0, all facilities are closed and all clients are unconnected. While time proceeds we increase all variables of unconnected clients uniformly such that if a client j is unconnected at time t we have α j = t at this time.We have to maintain the feasibility of the solution. There are two types of events at time t which can violate the feasibility.The first type of event happens when there is a unconnected client j and (i, j) ∈ M such that α j = d 2 (i, j). In this case we declare (i, j) to be tight. If facility i is open we declare j to be connected to i. Otherwise from time t on we have to maintain the constraint α j -β ij ≤ d 2 (i, j) by starting to increase β ij at the same rate as α j .The second type of event happens when there is a facility i such that (i,j)∈M β ij = f (i). In this case we declare facility i to be open. Furthermore all unconnected clients j with (i, j) tight are declared to be connected to i.We stop the process when all clients are connected. Let C ′ be the set of open facilities at the end of this process. For a client j let σ ′ (j) = i if j is declared connected to facility i. Then (C ′ , σ ′ ) is a feasible solution to the facility location problem with rad(C ′ , σ ′ , d 1 ) ≤ R. We would like to bound the facility location cost fac(C ′ , σ ′ , d 2 ) in terms of j∈C α j . However it is not possible to upper bound the facility opening costs for facilities in C ′ , since for a client j there may be multiple facilities i ∈ C ′ for which β ij > 0. Thus α j pays for opening multiple facilities from C ′ . Therefore following the work of [41] we will close some of the facilities in C ′ such that in the end every client pays for opening at most one facility.To decide which facilities we close from C ′ we construct a graph G on C ′ as follows. We connect two facilities i, i ′ ∈ C ′ by an edge if there exists a client j with β ij > 0 and β i ′ j > 0. Then let C ′′ ⊂ C ′ be a maximal independent set in G. For a client j we assign a facility from C ′′ as follows.If there is a facility i ∈ C ′′ with β ij > 0 we set σ ′′ (j) = i and call j directly connected. Since C ′′ is an independent set, this facility is even unique. If there is no such facility in C ′′ , we consider the facility i which j is assigned to in (C ′ , σ ′ ), i.e., i = σ ′ (j). If i ∈ C ′′ we set σ ′′ (j) = i and call j directly connected. Otherwise we know by maximality of C ′′ that there exists a facility i ′ ∈ C ′′ which is connected to i by an edge. In this case we set σ ′′ (j) = i ′ and call j indirectly connected. Lemma 46. For the solution (C ′′ , σ ′′ ) computed by the algorithm we obtain3 i∈C ′′ f (i) + j∈D d 2 (j, σ ′′ (j)) ≤ 3 j∈D α j and rad(C ′′ , σ ′′ , d 1 ) ≤ 3R.Proof. Let D 1 ⊂ D be the set of directly connected clients and D 2 ⊂ D be the set of indirectly connected clients.For a facility i ∈ C ′′ we know thatf (i) = (i,j)∈M β ij = i∈D1 : i=σ ′′ (j) β ij .Where the first equality holds, because i was declared open by the algorithm and the second equality holds, because all clients j ∈ D with β ij > 0 have to be assigned to i by σ ′′ and are directly connected.Let j ∈ D and i = σ ′′ (j). If j is directly connected we know that (i, j) ∈ M andα j = β ij + d 2 (i, j).If j is indirectly connected we claim that d 2 (i, j) ≤ 3α j . Let i ′ = σ ′ (j), since j is indirectly connected, we know that i and i ′ are connected by an edge in G. Thus there must be a clientj ′ ∈ D with β ij ′ > 0 and β i ′ j ′ > 0. We know that α j ′ = β ij ′ + d 2 (i, j ′ ) and α j ′ = β i ′ j ′ + d 2 (i ′ , j ′ ), so therefore d 2 (i, j ′ ) ≤ α j ′ and d 2 (i ′ , j ′ ) ≤ α j ′ .Let t be the time when facility i is declared open by the algorithm and t ′ the time when i ′ is declared open by the algorithm. Since j ′ is declared to be connected as soon as it has a tight edge to an open facility, we know that j ′ is connected at time min{t, t ′ } and therefore α ′ j ≤ min{t, t ′ }. On the other hand we know that t ′ = α j , since σ ′ (j) = i ′ . In total we obtain by triangle inequality, thatd 2 (i, j) ≤ d 2 (i, j ′ ) + d 2 (j ′ , i ′ ) + d 2 (i ′ , j) ≤ 2α j ′ + α j ≤ 3α j .Altogether this implies3 i∈C ′′ f (i) + j∈D d 2 (j, σ ′′ (j)) = 3 i∈C ′′ j∈D1 : i=σ ′′ (j) β ij + j∈D1 α j -β σ ′′ (j)j + j∈D2 3α j ≤ 3 j∈D1 β σ ′′ (j)j + j∈D1 α j -β σ ′′ (j)j + j∈D2 3α j ≤ 3 j∈D α j .This yields the first part of the lemma.For the second part let j be a client and i = σ ′′ (j). We have to prove that d 1 (i, j) ≤ 3R. If j is directly connected we have (i, j) ∈ M which implies d 1 (i, j) ≤ R. If j is indirectly connected let i ′ = σ ′ (j). Notice that this implies (i ′ , j) ∈ M . Since j is indirectly connected, we know that i and i ′ are connected by an edge in G. Thus there must be a client j ′ ∈ D with β ij ′ > 0 and β i ′ j ′ > 0 and therefore (i, j ′ ), (i ′ , j ′ ) ∈ M . We obtaind 1 (i, j) ≤ d 1 (i, j ′ ) + d 1 (j ′ , i ′ ) + d 1 (i ′ , j) ≤ 3R.We are now able to prove the theorem. Theorem 45. Given a set of facilities F with opening costs f (i) ≥ 0 for i ∈ F , clients D, two metrics d 1 , d 2 on F ∪ D and a number R > 0. If there exists a solution (S, τ ) with rad(S, τ, d 1 ) ≤ R, then we can compute a solution (C, σ) in polynomial time such that rad(C, σ, d 1 ) ≤ 3 • R and3 i∈C f (i) + j∈D d 2 (j, σ(j)) ≤ 3 • fac(S, τ, d 2 ).Proof. Since (S, τ ) is an integral solution to the LP with radius R, we know that the above algorithm computes a solution α for the dual LP with j∈D α j ≤ fac(S, τ, d 1 ). Let (C ′′ , σ ′′ ) be the solution for facility location computed by the algorithm. We can apply Lemma 46 to see that rad(C ′′ , σ ′′ , d 1 ) ≤ 3 • R and3 i∈C ′′ f (i) + j∈D d 2 (j, σ ′′ (j)) ≤ 3fac(S, τ, d 2 ).Given some radius R > 0 and a set of points P. We originally wanted to compute an optimal k-median solution of P with respect to d 2 under the side constraint that the radius of every emerging cluster is at most R with respect to d 1 . We consider the following formulation of the k-median problem as a linear program with the additional constraint that a point can only be assigned to a center if it is at distance at most R. Let M = {(i, j) | i, j ∈ P, d 1 (i, j) ≤ R} be again the set of all such combinations. We consider the following linear program. minimize(i,j)∈M d 2 (i, j)x ij subject to (i,j)∈M x ij ≥ 1 ∀j ∈ P x ij ≤ y i ∀(i, j) ∈ M i∈F y i ≤ k x ij ≥ 0 ∀(i, j) ∈ M y i ≥ 0 ∀i ∈ PIts dual is then given by maximizej∈P α j -zk subject to α j -β ij ≤ d 2 (i, j) ∀(i, j) ∈ M (i,j)∈M β ij ≤ z ∀i ∈ P α j ≥ 0 ∀j ∈ P β ij ≥ 0 ∀(i, j) ∈ M z ≥ 0Let (x ⋆ , y ⋆ ) and (α ⋆ , β ⋆ , z ⋆ ) be optimal solutions for the above linear program and its dual. We relax the constraint that restricts the number of centers by k. Instead as in [41] we introduce a cost f for opening a center. This yields an instance for the facility location problem where the set of clients D and facilities F equals P and the cost for opening a facility equals f . We can use Theorem 45 to compute a facility location solution (C, σ) for this instance. Let (α, β) be the respective solution for the dual program computed by the algorithm, then j∈P d 2 (j, σ(j)) ≤ 3( j∈P α j -f |C|). Thus if |C| = k we see that (α, β, f ) is a feasible solution for the dual program with cost j∈P α j -f |C| and therefore med(C, σ, d 1 ) = j∈P d 2 (j, σ(j)) ≤ 3( j∈P α j -f |C|) ≤ 3( j∈P α ⋆ j -z ⋆ k) = 3 j∈P d 2 (i, j)x ⋆ ij .However we cannot rely on the existence of facility cost f such that the algorithm for facility location outputs a solution with exactly k centers. Instead for ϵ > 0 we can find via binary search cost f 1 such that the respective solution (C 1 , σ 1 ) for facility location consists of k 1 < k centers and the cost f 2 such that the respective solution (C 2 , σ 2 ) for facility location consists of k 2 > k centers and |f 2 -f 1 | ≤ ϵ 2 dmin 3n where d min = min i,j∈P,i̸ =j d 2 (i, j). We slightly modify the randomized rounding algorithm by [41] for k-median to select k centers C ⊂ C 1 ∪ C 2 such that in the end we obtain a solution with E(med(C, σ, d 2 )) ≤ 6 j∈P d 2 (i, j)x ⋆ ij and rad(C, σ, d 1 ) ≤ 9R. We only explain the randomized rounding and do not go into detail about the binary search for f 1 and f 2 and the derandomization of selecting C ⊂ C 1 ∪ C 2 , since this can be done analogously to [41] .The randomized rounding works as follows: Let a = k2-k k2-k1 . Furthermore for i ∈ C 1 consider the setT i = {i ′ ∈ C 2 | σ -1 1 (i) ∩ σ -1 2 (i ′ ) ̸ = ∅} ⊂ C 2 . For every i ∈ C 1 let c(i) = argmin i ′ ∈Ti d 1 (i ′ , i) and set C ′ 2 = {c(i) | i ∈ C 1 } ∪ T where T is an arbitrary set of centers from C 2 \ C ′ 2 such that in the end |C ′ 2 | = k 1 . Let S be a set of cardinality k -k 1 chosen uniformly at random from C 2 \ C ′ 2 .With probability a we set C = C 1 ∪ S. For a point j ∈ P if σ 2 (j) ∈ S we set σ(j) = σ 2 (j) and otherwise σ(j) = σ 1 (j). With probability 1 -a we set C = C ′ 2 ∪ S. For a point j ∈ P if σ 2 (j) ∈ C, we set σ(j) = σ 2 (j) and otherwise σ(j) = c(σ 1 (j)).The difference to the rounding procedure in [41] lies in the choice of C ′ 2 . To ensure that the radius with respect to d 1 can be bounded, we are not allowed to simply set C ′ 2 as the set of points in C 2 closest to C 1 . With a simple modification for C ′ 2 we can ensure that both the k-median cost and the radius can be bounded. Lemma 47. We have E(med(C, σ, d 2 )) ≤ (6 + 2ϵ) (i,j)∈M x ⋆ ij d 2 (i, j) and rad(C, σ, d 1 ) ≤ 9R.Proof. For a point j ∈ P we distinguish two cases. Ifσ 2 (j) ∈ C ′ 2 then E(d 2 (j, σ(j)) = a • d 2 (j, σ 1 (j)) + (1 -a) • d 2 (j, σ 2 (j)). If σ 2 (j) ∈ C 2 \C ′ 2 then with probability k-k1 k2-k1 = 1 -a we have σ 2 (j) ∈ C and d 2 (j, σ(j)) = d 2 (j, σ 2 (j)), with probability a 2 we have σ 2 (j) / ∈ C, σ 1 (j) ∈ C and d 2 (j, σ(j)) = d 2 (j, σ 1 (j)).With the remaining probability a(1 -a) we haved 2 (j, σ(j)) = d 2 (j, c(σ 1 (j))) ≤ d 2 (j, σ 1 (j)) + d 2 (σ 1 (j), c(σ 1 (j))) ≤ d 2 (j, σ 1 (j)) + d 2 (σ 1 (j), σ 2 (j)) ≤ 2d 2 (j, σ 1 (j)) + d 2 (j, σ 2 (j)).Where the second inequality holds because σ 2 (j) ∈ T σ1(j) and c(σ 1 (j))) is the closest center to σ 1 (j) among all centers in T σ1(j) . In total we obtainE(d 2 (j, σ(j))) ≤ (1 -a)d 2 (j, σ 2 (j)) + a 2 d 2 (j, σ 1 (j)) + a(1 -a)(2d 2 (j, σ 1 (j)) + d 2 (j, σ 2 (j))) ≤ 2(ad 2 (j, σ 1 (j)) + (1 -a)d 2 (j, σ 2 (j))). Therefore E( j∈P d 2 (j, σ(j))) ≤ 2(a j∈P d 2 (j, σ 1 (j)) + (1 -a) j∈P d 2 (j, σ 2 (j)).It is left to provea j∈P d 2 (j, σ 1 (j)) + (1 -a) j∈P d 2 (j, σ 2 (j) ≤ (3 + ϵ) (i,j)∈M x ⋆ ij d 2 (i, j).Let (α (i) , β (i) ) be the solution for the dual facility location LP associated with the solution (C i , σ i ) for i = 1, 2. Observe that by Lemma 46 we haveEQUATIONEQUATIONj -f 1 k 2 ) + ϵ 2 d min -ϵ 2 d min = 3( j∈P α (2) j -f 1 k 2 ).Finally we getEQUATIONEQUATIONj -f 1 k) ≤ (3 + ϵ) (i,j)∈M x ⋆ ij d 2 (i, j).Case 1:i∈I ′ \I 2 i-1 > i∈I\I ′ 2 i-1 .In this case we knowmean(C I , σ I , ∥•∥ 2 ) = i∈I 2 2i-2 β 1 + i / ∈I 2 2i-2 β 2 = i∈I\I ′ 2 2i-2 β 1 + i∈I∩I ′ 2 2i-2 β 1 + i∈I ′ \I 2 2i-2 β 2 + i / ∈I∪I ′ 2 2i-2 β 2 < i∈I ′ \I 2 2i-2 β 1 + i∈I∩I ′ 2 2i-2 β 1 + i∈I\I ′ 2 2i-2 β 2 + i / ∈I∪I ′ 2 2i-2 β 2 = i∈I ′ 2 2i-2 β 1 + i / ∈I ′ 2 2i-2 β 2 = mean(C I ′ , σ I ′ , ∥•∥ 2 )where the inequality holds because i∈I ′ \I 2 i-1 > i∈I\I ′ 2 i-1 and the β 1 > β 2 . This contradicts the assumption.Case 2:i∈I ′ \I 2 i-1 < i∈I\I ′ 2 i-1 .Here we analogously get med(CI , σ I , ∥•∥ 2 ) < med(C I ′ , σ I ′ , ∥•∥ 2 ), which also contradicts the assumption.By the construction of P we know that (C I , σ I ) cannot be dominated by any other solution (C, σ). It is easy to observe that if M i contains a center that it is always better to assign all other points within this center independently whether we consider the k-median or k-means objective. Thus for any Pareto-optimal solution (C, σ) that dominates a solution (C I , σ I ) there exists a non-empty set U of indices such that for all i ∈ U there is no center chosen within M i . At the same time the other k -|U | scaled versions of M contain |U | additional centers. Thus we might remove arbitrary centers from these until every M j contains only a single center, choose an arbitrary center in M i for any i ∈ U and for all j ∈ {0, ..., k -1} reassign all points in M j to the respective center. For each index i ∈ U the k-median assignment cost of any point in M i gets reduced from at least ∆ -δ • 2 k-1 to at most δ2 k-1 . At the same time the assignment cost of any point contained in a cluster where a point gets removed increases by at most δ • 2 k-1 while the cost of the remaining nodes stays the same. Thus the k-median cost decreases by at least |M ||U |(∆ -3δ2 k-1 ) > 0. A similar statement can be shown for the k-means objective. Thus the respective solution would not have been Pareto-optimal which is a contradiction which means that for any I the solution (C I , σ I ) is Pareto-optimal and the lemma follows.In the following we see one possible example for the construction M . Example 50. Consider 5 points on a line, where the distance between the first three points and the second point is 1 and the distance between the second and the third point is 2 (see Figure 6 ). Then the optimal median center is one of the leftmost points, while the optimal mean center is the single point in the middle. Therefore α 1 = 4, α 2 = 5, β 1 = 10 and β 2 = 7, fulfilling the prerequisites on M .Even though the Pareto set of this combination may have exponential size, Papadimitrou and Yannakakis [49] showed that there always exists an (1 + ϵ, 1 + ϵ)-approximate Pareto set, whose size is polynomial in the input size and 1 ϵ . They furthermore showed that there is a polynomial algorithm to construct such an (1 + ϵ, 1 + ϵ)-approximate Pareto set if and only if one is able to solve the following problem in polynomial time: Given the instance and b 1 , b 2 ∈ R, either find a solution s with f i (s) ≤ b i for i ∈ {1, 2} or report that there is no solution s with (1 + ϵ)f i (s) ≤ b i for i ∈ {1, 2}. Unfortunately, for f 1 , f 2 ∈ {med, mean} it is unknown whether this problem can be solved efficiently.From now on, we focus on finding an approximate convex Pareto set instead. Since in the following we only consider cases where α 1 = α 2 , we write CP α instead of CP α,α for convenience. Theorem 51. Given a finite set P, metrics d 1 , d 2 on P and two objectives f 1 , f 2 ∈ {med, mean}. Let ϵ > 0. Then we can compute an (δ + ϵ)-approximate convex Pareto set CP δ+ϵ in time that is polynomial in the input size and 1 ϵ , where δ = 2.67059 if f 1 = med and f 2 = med, and δ = 9 + ϵ if f 1 = med and f 2 = mean or f 1 = mean and f 2 = mean. The size of this set |CP δ+ϵ | is also polynomial in 1 ϵ and |P |.To do this, we make use of a scheme presented by Diakonikolas [22] . The idea is essentially to reduce a given multi-objective optimization problem to an associated problem with a single, combined objective.More formally, let f 1 , f 2 be two minimization objectives, and w = (w 1 , w 2 ) ∈ R 2 + a weight vector. Then we define the related Comb-problem to be the problem that seeks to minimize the weighted combination of both objectives w• f = w 1 • f 1 + w 2 • f 2 .We denote by Comb δ (w) a routine that returns a δ-approximate solution to the Comb-problem with weight vector w. We will show that a polynomial time Comb δ (w) routine is enough to compute a (δ • (1 + ϵ))-approximate convex Pareto set to the bi-objective original problem Π for all ϵ > 0. To achieve this, we will describe a scheme which returns such a set where the number of calls to the Comb δ routine is polynomial in 1 ϵ and the input size. The scheme and its proof are basically identical to the one Diakonikolas describes in his thesis [22] , where he showed that an (F)PTAS for the Comb-problem is sufficient to obtain an (F)PTAS to the convex Pareto set. In the following we show that the proof still works, if instead of an (F)PTAS for the Comb-routine we only have an approximate Comb δ -routine.A point s ∈ R 2 + is called approximately balanced if both its coordinates are within factor 2 of each other. We will first construct a set to (δ • (1 + ϵ))-cover all approximately balanced solution points S bal , and later use the fact that approximate convex Pareto sets are invariant under the scaling of their objectives to cover all solution points. First we observe that for all ϵ > 0 there is a set of size O( 1 ϵ ) that (1 + ϵ)-covers all approximately balanced solution points. We want to compute a δ-approximation to such a set using only O( 1 ϵ ) many calls to Comb δ . Therefore we are looking for a set of weight vectorsW bal with |W bal | ∈ O( 1 ϵ ) whose corresponding solution set Q bal = {Comb δ (w) | w ∈ W bal } contains a (δ • (1 + ϵ))-approximate convex Pareto set of S bal .We will now define the set W bal in a way, that is only dependent on ϵ, but not on the given problem instance. For that purpose, we set The following lemma shows that the set Q * bal is in fact a (δ • (1 + ϵ))-approximate convex Pareto set for all approximately balanced solution points. Lemma 52. For every approximately balanced solution point s ∈ S bal , there is a convex combination of points in Q * bal that (δM = ⌈ 2 ϵ ⌉. Let W bal = {(1, l M ), ( l M , 1) | l ∈ [M ]}. It is easy to see that |W bal | ∈ O(• (1 + ϵ))-covers it.Proof. We first prove the following claim: For any weight vector w ∈ R 2 + there is a solution q * ∈ Q * bal such that w • q * ≤ δ(1 + ϵ)w • s. Let w = (w 1 , w 2 ) be an arbitrary weight vector. By symmetry and by scaling of the weights we can without loss of generality assume that w 2 ≤ w 1 = 1. Let w * be (w 1 , w * 2 ), where w * 2 arises from w 2 by rounding up to the next higher multiple of 1 M . It follows that w * ∈ W bal and therefore was considered by our scheme. Let q * be the solution point given by Comb δ (w * ).By the definitions of w * and of Comb δ the following holds:EQUATIONEQUATION≤ δ • (1 + ϵ)ws,where inequality (2) follows from the fact that s is approximately balanced and inequality (3) follows from the fact that w 1 = 1 and therefore s 1 contributes directly to ws. This proves the claim.Let q = (q 1 , q 2 ) be the point that lies on the border of the convex hull of Q * bal and fulfills q1 q2 = s1 s2 (therefore q intersects the line between s and the origin). Let q l , q r be the solutions in Q * bal such that q l 1 ≤ q 1 ≤ q r 1 and there is no p ∈ Q * bal with q l 1 ≤ p ≤ q r 1 . Let (1, w l ), (1, w r ) be the weights that generated q l and q r , respectively.Then we know that for all weights between w l and w r either q l or q r are approximately optimal (since w • p is linear in p and w for all w, p). Therefore there is a w = (1, w * ) with w r ≤ w * ≤ w l such that w • q l = w • q r and both points are approximately optimal for this weight. Since q is a convex combination of q l and q r we know that w • q = w • q l ≤ δ(1 + ϵ)w • s. Together with q1 q2 = s1 s2 it follows that s is approximately dominated by q which is a convex combination of q l , q r ∈ Q * bal .Since normally not all solution points are approximately balanced, Q * bal might not cover all solution points. Diakonikolas shows that this can be taken care of by looking at multiple different scalings of the objective functions such that for each point s of the solution space there is one scaling such that s is approximately balanced in the scaled version. He furthermore shows that a polynomial number of scalings is sufficient. This proves that for all ϵ > 0 one can construct a ((1 + ϵ) • δ)-convex Pareto set whose size is polynomial in ϵ if there is a polynomial Comb δ -routine. The runtime of this construction is also polynomial in 1 ϵ for two objectives. All that is left to do in order to prove the theorem is to show that there exist Comb routines that yield the desired approximation factors to the different combinations of objective functions.Lemma 53. Let d 1 , d 2 be two metrics. Then the following hold:1. There is a Comb 2.67059 -routine for f 1 = med and f 2 = med.2. For all ϵ ′ > 0 there is a Comb 9+ϵ ′ -routine for f 1 = med and f 2 = mean.3. For all ϵ ′ > 0 there is a Comb 9+ϵ ′ -routine for f 1 = mean and f 2 = mean.1. Since for any weight vector w ∈ R 2 + the function d ′ = w 1 • d 1 + w 2 • d 2 is again a metric, the Comb-problem can be solved by any approximation algorithm for the k-median problem under general metrics. The currently best known algorithm is from Cohen-Addad et al. [16] and achieves an approximation factor of 2.67059. Ahmadian et al. [4] extends to all sumbased cost functions of the form p∈P c(p, σ(p)) whose distance function c(i, j) fulfills the inequality c(i, j) ≤ 3(c(i, k) + c(k, l) + c(l, j)). The combined objective for the kmeans and k-median cost-functions for an arbitrary weight vector w ∈ R 2 + is given by w 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: Many of our experiments were deterministic and thus require no error bars and similar measures. The only algorithms using randomization were those incorporating k-means++ for which we provided the variance in Table 14 .Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: Most experiments were executed on everyday computers with negligible running time as the experiments were not very computation heavy. For completeness we added the exact configurations of the used computers as well as giving a reasonable bound of the time of execution.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: All the data we used are properly cited and we provided the respective URLs where we found the data set. We also complied to the respective terms of service. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: The main assets introduced in this paper are the algorithms which are described and analyzed thoroughly in the respective sections. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. We treat k as an exact bound (except for the somewhat different msr objective). For minimization problems, choosing ≤ k or = k centers makes no difference since splitting clusters improves the cost. We prefer = k centers because otherwise, combinations with k-separation would include a trivial Pareto-optimal solution that just constructs one cluster P with infinite separation.(a) Geography based clustering. (b) The 54-th Pareto solution. (c) Time series based clustering. 
 
 Appendix:  


Decision: This paper gives various bounds for the Pareto approximation of k-clustering problems.

Summarizing the discussion, the notion of Pareto approximation was proposed before, and the main contribution of this paper greatly expands the range of problems that admit such approximation. The motivation in practical applications are justified by concrete examples. However, the ratios/results are not an improvement/incomparable to previous results, and the techniques are not particularly novel. The writing should be improved to better position the contribution of the paper.

Overall, I think this paper presents a set of interesting results, and the general direction may be of interest for future research. I thus recommend for accept.

Reviews: review: paper_summary: paper_summary: The paper introduces novel algorithms to approximate the Pareto-optimal solutions for bi-objective k-clustering problems. The authors focus on combinations of clustering objectives such as k-center and k-means, or k-center with two different metrics. Usually, these objectives are conflicting and cannot be optimized simultaneously, making it necessary to find trade-offs. The algorithms provide provable approximation guarantees and are demonstrated through experiments to yield good clustering that single-objective approaches fail to capture.
strength_weakness: strength_weakness: 1. It is not entirely clear the main novelty aspect of the work. In the setting of sec 2.1 where k-sep is combined with other objectives, the main takeaway seems to be that the authors were able to integrate existing state-of-the-art guarantees into their framework. Similarly for other sections for Pareto-optimal solutions were discussed, the authors leverage relies heavily on already existing approaches.
2. Most results are either incomparable with respect to the related work, because of bicriteria guarantees or translate to the existing guarantees. The results section should succinctly describe the main technical contributions (even if a few) for a better understanding of technical innovations.
questions: questions: I would request the authors to clarify the main technical innovations in this work -- e.g., in 229: "The input to the algorithm now consists of clusters instead of single points". Does it require substantial change in techniques?

Pareto-optimality makes sense for multi-objective guarantees. But falling back on bi-criteria guarantees also might defeat the purpose. Is there a way to reconcile both and argue about them?

The approximate pareto-optimal sets-based approaches rely heavily on existing works. Can you please highlight the challenges or technical innovations in adopting it to the set of problems considered.
limitations: limitations: N/A
paper_summary: paper_summary: This paper presents a novel framework for clustering pareto optimization. This paper studies the approximately pareto-optimal solutions for bi-objective k-clustering problems. The authors focus on the computationally very efficient single linkage / must-link constraints and the computation of pareto-optimal solutions. They first establish that it is not possible to simultaneously approximate k-separation and any of the minimization problems to constant factors. By iterating through all pairs of possible separation and possible radius/diameter, they obtain the approximate Pareto set. The authors also give the results combining k-center or k-diameter with a k-clustering minimization problem, and give the results combinations of k-median and k-means.
strength_weakness: strength_weakness: 1. This paper is not very motivated. The authors seem not explain the motivation for studying the pareto-optimal algorithm for the clustering problem. Moreover, the authors did not give the motivation why the combination of these clustering objectives is studied.

2. The authors seem not conduct experiments on large-scale datasets, such as 100 million points. Moreover, there are also faster version of k-means++ method, such as the rejection sampling method proposed in [1] and random projection based k-means++ method proposed in [2]. The author did not consider comparative experiments with these algorithms.

3. The algorithms have polynomial running time. As far as we know, the pareto optimization of other problems can be done in linear time.

4. Some sections, particularly those involving heavy mathematical notation and proofs, could be made clearer with additional explanations or visual aids. This would make the paper more clear.

[1] Cohen-Addad V, Lattanzi S, Norouzi-Fard A, et al. Fast and accurate k-means++ via rejection sampling[C]//Proceedings of the 34th International Conference on Neural Information Processing Systems. 2020: 16235-16245.

[2] Charikar M, Henzinger M, Hu L, et al. Simple, scalable and effective clustering via one-dimensional projections[C]//Proceedings of the 37th International Conference on Neural Information Processing Systems. 2023: 64618-64649.
questions: questions: Q1: Why do the authors give this definition of pareto-optimal solutions for bi-objective clustering? The authors should explain the motivation of proposing this definition.

Q2: The authors focus on the single linkage/ must-link constraints. The authors should explain the significance of these constraints and give the comparison with a single objective.

Q3: Can the authors provide more detailed real-world applications where these bi-objective clustering algorithms would be particularly beneficial? 

Q4: Do these experiments have scalability on large datasets? The authors should give some experiments on large-scale datasets. Moreover, the authors should add comparative experiments with other basic clustering algorithms.
limitations: limitations: This paper is mainly a theoretical result, and there is no negative societal impact.
paper_summary: paper_summary: This work develops efficient algorithms to approximate the Pareto-optimal set for different bi-objective clustering problems with solid theoretical guarantees. The problem can have different clustering objectives (e.g., k-separation, k-center, k-diameter, k-median, k-means, k-MSR) and/or different metrics (e.g., different distance measures).  

Two different types of algorithms are considered in this work to (1) approximate the whole Pareto set for problems that combine k-separation with various k-clustering minimization objectives or combine k-center/k-diameter with a k-clustering minimization problem, and (2) approximate the convex Pareto set (e.g., the convex hull of the ground truth Pareto set) for problems that combine k-median and k-means, where the Pareto set can be exponentially large.

Thorough and comprehensive theoretical analyses are provided to support and demonstrate the efficiency of the proposed algorithms. Experimental results show that the proposed algorithms can achieve promising performance on different bi-objective clustering problems.
strength_weakness: strength_weakness: I enjoy reading this paper and do not see any obvious weakness of this work. Below are some minor concerns and questions.

**1. Centers Chosen from the Point Set** 

One limitation of the proposed algorithms is that the clustering centers can only be chosen from the point set. I can understand the necessity of this requirement when we hope to approximate all Pareto solutions (up to $O(n^2)$ with this requirement) in subsection 2.1 and subsection 2.2. 

However, it is not clear whether this restriction is still necessary when we want to approximate the convex Pareto set in section 2.3. What is the challenge for this case if we are allowed to choose the center from an ambient metric space? 

**2. Extension of the LP Rounding Algorithm**

As mentioned in the related work section, Alamdari and Shmoys (2017) leverage the LP rounding algorithm by Charikar et al. to handle the bi-objective clustering problem with k-center and k-median, while this work uses the primal-dual algorithm by Jain and Vazirani (2001). I am curious whether the LP rounding algorithm can be extended to tackle (some of) the other settings considered in this work.

In addition to the incomparable approximation factor, what are the pros and cons between the LP rounding algorithm and the primal-dual algorithm used in this work for multi-objective clustering?

**3. Generalization to more than Two Objectives**

This work focuses on bi-objective clustering, but many real-world applications might involve more than two objectives. What makes it hard to generalize the current methods to handle more objectives for approximating the Pareto set or convex Pareto set?

**4. Minimum Cardinality Set**

It seems that the proposed methods in this work do not consider minimize the cardinality of the approximate solution set. Can these methods be further extended to find the smallest (minimum cardinality) approximate Pareto set as discussed in Diakonikolas (2011)? 

**5. Finding the Most Suitable Solution**

The number of solutions found by the proposed methods for a given method can still be large. How can we efficiently find the best solution for each application (e.g., the best clustering in Figure 4)? Since the ground truth clustering is unknown, we cannot calculate the quality metric (e.g., Normalized Mutual Information and Rand Index) for each solution. Will the users have to check all the solutions themselves and then choose the most suitable one?

In addition, how can the clustering number $k$ be properly chosen for real-world multi-objective clustering problems?

**6. Order of the Problem Settings**

There is a mismatch between the order of problem settings in the main paper and the appendix. In the main paper, the order or problems is 1) k-separation + k-clustering minimization, 2) k-center/k-diameter + k-clustering minimization, and then 3) combination of k-median and k-means. However, in the appendix, the order is A) combination of k-clustering minimization , and then B) combinations involving k-separation. What is the reason for this choice?

**7. Publication Venue**

*(This part will not affect my decision.)*

This work conducts a comprehensive study on multi-objective clustering, which is not possible to be compressed into a 9 (or 10 in camera-ready) page conference paper. Many important materials (e.g., algorithms, all theorems, and theoretical analyses), which are actually the crucial contributions of this work,  have to be put in the supplemental materials. There is also no room left for a conclusion section. 

I think a journal like JMLR should be a more suitable choice to publish this work.
questions: questions: See weaknesses.
limitations: limitations: This work has discussed its limitations in the introduction (page 2, objectives subsection), but I think an explicit limitation subsection could be much more helpful.

Comments: title: Rebuttal
Please respond to the rebuttal
comment: Thanks for answering my questions -- they clarified some of the questions I had with regards to novelty. 

However, I do want to point out to the authors, that the presentation of the paper requires significant reworking to bring out the main technical contributions, for others in the research community to appreciate (or even understand) the technical contributions/results. 

After reading the rebuttal responses, I'm increasing my score.
Dear reviewer CrwW,

Can you please read and comment on the rebuttal from the authors? Also, since we have a somewhat mixed rating, please take other reviews and responses into consideration.

Regards,
Area Chair
Thank you for your comment. Could you maybe give us a little more detailed response on why you prefer to maintain your negative score? We would be very interested to know what the remaining criticism is.
Thank you for your response. However, after carefully considering your points, I prefer to maintain the original score.
Thank you for the thorough response. All my concerns have been properly addressed, so I keep a positive score (7) at this stage.