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 2024 poster (2024)
Keywords: multi-criteria clustering
approximation algorithms
Pareto-optimal solutions
k-means
single linkage
k-median
k-center
Primary area: optimization
TL;DR: We develop novel algorithms for approximating the set of Pareto-optimal clusterings for various combinations of two objectives.

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.

Approximately Pareto-optimal Solutions for Bi-Objective - k-Clustering Problems
Anna Arutyunova
Jan Eube University of Bonn Bonn, Germany eubeêcs. unw. de
Heinrich Heine University Düsseldorf
Düsseldorf, Germany
anna arutyunova@hhu.de
Heiko Röglin
Melanie Schmidt
University Bonn
Heinrich Heine University Düsseldorf'
Bonn, Germany roeglinêcs.. uni-bonn.... de
Düsseldorf, Germany
ms mschmidt www.tthhhhheemm de
Sarah Sturm University of Bonn Bonn, Germany sturmθcs. uni-bonn de
Julian Wargalla
Heinrich Heine University Düsseldorf
Düsseldorf, Germany
julian. wargalla@hhu.dee
Abstract
As a major unsupervised learning method, clustering has received 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. How- ever, in applications, is common that good clusterings should optimize multiple objectives (e.g., visualizing data on 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 optimizing k-center with respect to two different metrics. Usually these objectives are conficting and cannot optimized simul- taneously, making it necessary to find trade-offs. We develop novel algorithms for upproximating the set of Pareto-optimal solutions for various combinations two objectives. Our algorithms achieve provable approximation guarantees and we demonstrate in several experiments that the approximate Pareto front contains good clusterings that cannot be found by considering one of the objectives separately.
Introduction
Clustering is major unsupervised learning method that is used to find structure 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 describe good clustering, but objectives that correspond that description for the case of metric clustering are the k-diameter problem and Single Linkage clustering.
In the k-diameter problem, to find partition of P into & clusters that minimizes the maximum diameter of any cluster. This models the first problem: Finding clusters where the objects in the same cluster 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,
given point set P from metric space and number & and want
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table State-of-the-arr approximation factors
objective
rad / diam
med
mean
best guarantee / reference
2/ 30 37
2.67059
[66]
9 +
3
i.e., ensuring that points in different clusters are dissimilar? Certainly not, as the small example in Figure[] An optimal k-diameter clustering with k has radius A, but 22 and Iy are very close together in this solution.
Single Linkage clustering is linkage method that finds the clustering which the minimum distance between any two clusters maximized, Le., it focuses the second goal. We refer to the problem of maxi- mizing the minimum inter-cluster distance as the k-separation problem in the following, i.e., Single Linkage is optimal algorithm for the k-separation problem. In Figure with = 2, Single Linkage computes the clustering {{21, 22, , {2aa} } or the symmetric clustering.
A
21
322 33
2/4
Figure 1: toy example.
Unfortunately, there is an inherent tension be- tween the k-diameter and k-separation problem, even the points are on the Euclidean line R. In Figure [ we could observe that the optimal k-separation clustering is still a very good k- diameter clustering (assuming to be small).
A
Figure 2: The set 23. for k =
However, one can construct examples where the two cost functions cannot be reconciled:
Example For any fixed (O...., k(k - 1} Figure illustrates this for k = 3. Now the only way to obtain minimum inter-cluster distance of 1 is to use k k- singleton clusters (any other clustering needs to break A and has separation of 1/k). Notice that this clustering has maximun diameter of (k- since that is the diameter of A. However, the best k-diameter clustering divides the points into intervals equal length, achieving a diameter of ((-- 1)2 (k 1)) k- which is smaller by a factor of k -1.
consider the set Xx = (1....,k k 1} U with A (-x/k
... {k-11) 1} and one cluster for A
Example demonstrates that the natural goal of clustering is inherently goal with two potentially conflicting objectives. Our formalization with k- k-diameter and k-separation is an example of bi-objective clustering problem.
This is only one motivation for studying multi-objective (or bi-objective) clustering. Clustering with respect 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, df be a metric space. Given C C P with |C| k
and an assignment o: + C we define the following objective functions:
k-center: (C, d) = maxpep (p))
k-diameter: diam(C, a, d) maxp.geP: a(p)=a(g) d(p.
k-median: med(C, o, Eper d(p, a(p))
k-means: mean(C, a. d) = Σpep d8 (p.
k-min sum radii (k-msr): msr(C, = Ecec maxpeo- d(c,p)
k-separation: sep(C, a, d) min (())t(()) d(p,9)
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 a induces; we use the same notation here for convenience and introduce additional notation in the respective technical sections). Each objective induces optimization problem when we fix the number of clusters & e N we want to

---

obtain [ The seseparation problem is a maximization problem, all other objectives are to be minimized, i.., the aim is compute set C' with & centers and an assigmment function o with (c) * 0 for all e E C' such that the respective objective function is low as possible. All the minimization problems are NP-hard and also NP-hard to optimize to arbitrary precision [7 31 positive side, approximation algorithms with small constant factors are known for all the minimization problems mentioned, see Table (all numbers are for the general metric case, including k-means). The s-separation maximization problem can be solved optimally by running the well-known Single Linkage algorithm until the given number & of clusters is left.
On the
Use Cases We have two different use cases: 1) Simultaneously optimizing a well-known k- clustering 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 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
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 constrained clustering problem), or soppuuing/appoximaain the Pareto front. We follow the latter approach and focus on algorithms to approximate the Pareto front bi-objective clustering problems. Let us first define this concept for- mally: Given two metrics d1, d2 on X' and two objectives fi, f2 E (rad, diam, med, mean, msr, sep), a solution (C, o) is dominated by a solution (C", o') if the following is true for both i = 1, 2: (C",, o', di) S f(CC,,, o, d,) if ft is minimization objective and fi(C", o', de) 2 fi(C, o, d.) if f: is a maximization objective, and in addition, for i = or = 2, the inequality is strict. A solution (C, or) is called Pareto-optimal if it is not dominated by any other solution. We denote by IP the set of all Pareto optimal solutions and call the Pareto set or Pareto front.
Notice that by definition the Pareto front contains solution (C,, 02) optimizing objective f: for i 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 a = (a1, (2) ) E IR.2, set Pa is an a-approximate Pareto set if the following is true: For every Pareto-optimal solution (C,
IP, there
is a solution (C", E Fo, that is an a-approximation to (C,o), i.e., f.(C", o', < asfi( (C, o, de) f E (1,2} if fi is minimization objective and fi(C", d.) 2 (1/os)fi(C,, de) for i if ft is a maximization objective. Figure 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 33. 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 solution lies to the right and above the corresponding point.
{1
While other approaches for multi-objective optimization (like optimizing weighted sum of the objectives or solving a constrained clustering problem) produce single trade-off of the objectives, an important advantage of the approximate Pareto front is that it consists of a diverse set of trade-off's. This is beneficial for data analysis because it offers more information and ficxibility to the data analyst. In particular, approximate Pareto front contains for any weighting of the objectives approxi- mately 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.
We treat as an exact bound (except for the somewhat different msr objective). For minimization problems, clusters improves the cost. We prefer =
choosing < k or = & centers makes no difference since splitting centers because otherwise, combinations with k-separation would include a trivial Pareto-optimal solution that just constructs one cluster P with infinite separation.
3

---

1.2
Pawii Pants
1000
1200
Pareto Prints
Income Difference
800
0.0
200
0.2
200
255
100
150
420
470
500
550
Setour olien
Distance in km
(a) Approximate Pareto set for k-separation and k-means on the same metric, data set 2d- 10c-no4, see Section[..]
(b) Approximate Pareto set for k-center with
[Wo metrics described in Section 3.2 with
A: 16 clusters.
Figure 3: Examples of approximate Pareto sets copied from the later experimental sections.
Related work on Pareto sets 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 its approximation is small, it can be presented to a human decision maker or used in some other post-pros 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 [9] 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 a-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 clus- terings are used in applications. Popular techniques include, c.g., genetic algorithms (24] 42), multi-objective particle swarm optimization [TO] evolutionary algorithms [36]47) and combina- tions of k-means and fuzzy c-means (9]. All these heuristics have in common that they a guarantee on the approximation factor. We cannot review all the literature in this area and focus on what we perceive most related.
without
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, algorithm that computes a (4, apppoxxixoiiiiio of the Pareto front. Their algorithm uses an LP rounding approach based k-median LP with additional side constraint that restricts the radius of clusters to 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.65 6 + c). Alamdari and Shmoys also give 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 showing that least of the objectives can at best be Ω / -apprxximated.
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 enforcing 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 computationally more feasible way. Our focus is on the computationally very efficient Single Linkage / must-link constraints and the computation of Pareto optimal solutions.
we evaluate if the usage of orthogonal objectives can improve the performance of clustering with respect to recovering ground truth clustering. A similar approach is evaluated by Handl and Knowles in (35). The first objective studied there a k-means/kk-mdde type objective called deviation. The second objective is based on nearest neighbors and evaluates the
In Section 3.1
(and Section C.I

---

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 Section 3.I and also leads to improved F-measures. The focus of that work is still different as we focus provable approximations of the Pareto front.
For the evaluation in that same section, we 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 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 single robust clustering.
2 Results
We provide algorithms to compute the approximate Pareto set for most combinations of two clustering objectives fi, f2 E [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-
by Hochbaum and Shmoys [37] which we adapt to compute an approximate Pareto set for the combination of fi E {rad, diam, sep} and f2 E {rad, diam). We further incorporate the radius/diameter in the (6 - -ppproxxmmaioonnn for k-median (also yielding an (11)aaproxximation for k-means) by Jain and Vazirani 441 to obtain an approximate Pareto set for the combination of fi {rad, diam} } and fz E {med, mean]. We adapt the (3 + e)-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 s-separation. For the combinations of fi sep and f2 (med, mean] } we use existing algorithms to compute a solution which optimizes fi and a solution which optimizes f2 and combine them to good solution for both objectives, similar to the nesting technique described by Lin et al. [46). Lastly for the combinations of fı, f2 E (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 fi, E [rad, diam} we furthermore design 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 simultancously approximate k-separation and any of the minimization problems to constant factors. We 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-MR 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.
2.1 Combining k-separation with various k-clustering minimization objectives
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 practical evaluation of the i--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 ground truth clustering in our experiments.
Table gives an overview of our theoretical findings. An entry (1, means that we show how to compute the approximate Pareto set (a..).. More precisely: Let di and d2 be two metrics on the same point set, and let fz E {sep, rad, diam. med, mean, msr} be the second objective. Now let a (1, a) be the entry in the corresponding column of Table 2 Then this means that we can compute an a-approximate Pareto set P., with respect to sep with metric dj and f2 with metric d2. The second line refers to the corresponding theorem. All the individual theorems and their proofs are in the supplementary material.
5

---

Table 2: Results for combining k- k-separation with various objectives. Here 81 and 52 refer to the best known approximation guarantee for t-median/k-mmant currently ón = 2.67059/82 = 9 + [6 4
k-separation
k-center
k-diameter
k-median
k-means
k-MSR
k-sep. proof
(1,1)
(1,
(1,2) Thm.
(1, + 61
(1,44408 52)
(1,3
Thm.
Thm.
Thm. 12
Thm. 17
Thm. 24
Techniques 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²) possible optimal values. And if we fix value A to be the desired separation, then this means that all points x. with d(xr, y) < A have to in the same cluster because otherwise the objective is automatically below A. And we transitively merge all pairs y with d(x, y) < A, then we get a solution with objective value 2 A. So is well characterized how an optimal k-separation solution looks like (also see Lemma 3). To combine k-separation with other clustering objectives we first consider such a clustering with separation A, if it has already k clusters, there is nothing left to do. it has more than clusters we decide which clusters to merge based on the second clustering objective.
This immediately leads to the (1, -entry when combining two s-separation objectives (for different metrics): Iterate through all (nn") combinations of possible optimal objective values (A1. Ag). For each guess, merge z, y if d1 (z. y) < A or dz y) < A₂ (or both). While the running time can certainly be improved, this gives the full optimal Pareto front in polynomial time.
For f2 rad f2 diam, we also have that the optimum value of solution is pairwise distance between two points. Thus, there are also at most (nn)) possible values that f2 can take. There is a well-known algorithm due Hochbaum and Shmoys (37 that for any given radius I (or diameter) can produce a solution with at most double that value or prove that no solution with value ft exists. We adapt this algorithm work on the above clustering with Separation A 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, 2a-pprooieatee Pareto set. The details are discussed in Section AA2 of the supplementary material.
When combining sep with f2 med or f2 = mean (Supplementary Section A.3). we still know that the separation value A is one of Onn²) candidates. We use the above clustering with separation A and decide which clusters to merge further based on an approximate clustering with respect f2. 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 f2, the quality of our Pareto set depends on the approximation ratio of the algorithm for f2.
Finally, we combine sep with msr. This is the only place where we study msr it is less common than the other clustering objectives. is also the only objective where we deviate from the rule that clusters have to have = l clusters and allow < k clusters. We study it because it seems more aligned with k-separation than the other objectives. However, Obs. [1 reveals that also k-separation and k-MSR cannot be approximated simultaneously. In order to approximate the Pareto front, adapt the very recent state-of the---- algorithm for k-MSR approximation from 11 to our setting. That algorithm has an approximation ratio of 3 c and indeed, we show how compute (1,3 c)- approximate Pareto fronts. Buchem et al. [1]] 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 A, obtain a clustering with separation A, 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 taken into account when trying to cover them with balls. We discuss this in the supplementary material in Sec. A.4
2.2 Combining k-center or k-diameter with k-clustering minimization problem
Now we turn to combinations of popular k-clustering minimization problems. Table 3 lists combina- tions involving k-center or k-diameter. Again, let d and d2 two metrics on the same point set. Then let fi {rad, diam), let fa {rad, diam, med, mean] be the second objective. Finally, let

---

Table Results for combining rad and diam for two different metries or with a sum-based objective. k-center/k-
The combination of eeceter/k-diamette with k-separation can be found in Table 2
k-median
k-means
ereentr/k-diamettee proof
(2. 2)
(9.6 6 + c)
(18, 6
+
(9. <) (18, 54+
Cor. 37
Thm. 41
Cor. 44
Thm. 42
Cor. 44
(a, b) be the entry corresponding to fi and f2 in Table 3 Then this means that compute an a-approximate Pareto set aa. with respect to rad or diam with metric d1 and fz with metric d2. 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 (n²) 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²). This is tight since we were able to provide an instance where the optimum Pareto set has indeed a size of (2n²)) (Supplementary Section B.2 However it can be proven that there always exists (2, 2) a)appooximaioo of the Pareto front of size O(n).
We adapt well-known 2-approximation algorithm due to Hochbaum and Shmoys 37 A straight- forward adaption of this algorithm would iterate through O pairs (ri,12) of possible radii and check for each of them if a maximal independent set of size at most & can be found in an appropriate threshold graph. While this would result in a running time of (n ). we improve the running time by observing that only certain pairs (2),72) need to be checked (in total O(n²) many) and by updating the threshold graph dynamically. While updating the threshold graph can have a time complexity of 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 compute the approximate Pareto set (2,2) in time O(n"). The algorithm and its analysis also work for k-diameter, giving the same guarantees. For more details we refer to Section B. the supplementary material.
up to ((n²) in certain iterations, were able to
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 [4]] Alamdari and Shmoys [5] adapt the approxi- mation algorithm by Charikar et al. [12), which leads to a (4, -approoxieetee Pareto set. For recent algorithms 15 [6], incorporating radius requirements does not seem easily possible.
The primal dual algorithm gives (6 + appappoxiintiion guarantee for k-median and 54- approximation guarantee for k-means (the paper only states 108, but that is because the k-means problem is considered in IR 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 based on an I.P formulation where variables Tiy indicate that point ý is assigned center The adaptation starts by fixing radius R and removing all Tıj for which j(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 > clusters and small cost. In the combination step we have to ensure that the radius stays bounded (see Lemma 47) We can ensure 9-approximation with respect to the radius while keeping the original approximation factors for k-median/k mediaa 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.
2.3 Combinations of k-median and k-means
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 too large: Theorem 48 in the supplementary material shows that the combination of med and mean both with the same Fuclidean metric can lead to Pareto sets of exponential size. Similar examples can be constructed for f1 = f2 and fi E (med, mean) d1 * d2.
7

---

Table Number of points n, dimension d, and number of desired clusters & for all data sets in $3.1
name
Rice
Dry Bean
Wine
Optdigits
Iris
2d-4c-no3
2d-10c-no3
2d- 2d-10c-no4
ref
1
2
3
66
[26
344
[32
[34
n
3810
13611
178
5620
150
1123
3359
3291
d
7
16
13
64
k
2
7
3
10
4
10
10
possible approach to compute an approximate Pareto set is due to Papadimitrou and Yannakakis [49]. They showed that there always exists 6-approximate Pareto set whose size is polynomial in the imput size and 7 where e = (1+ 1,,1+e, 1+)'). There is a polynomial algorithm to construct such an e-approximate Pareto set if and only if one is able to solve the following problem in polynomial time: Given the instance and 61, by E I. find a solution with f((s) S b, for E {1, 2} or report that there b, for i E (1, 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.
is no solution with (1 + (s)
An alternative to approximate Pareto sets 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 weighted sum of the objectives. For two minimization objectives f1 and ʃ2, a solution (C, a) a supported Pareto- optimal solution if there exist weights W1, W2 > 0 such that (C, is solution for the objective Wi wi + w2f2 with minimum value. For a solution (C,or let F(C, o) = (fi(C, f2(C, o)) and F(P) {F(C, o) oC) E 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 supported Pareto- optimal solutions the convex Pareto set in the following. Diakonikolas [22] has also introduced the notion of approximate convex Pareto sets. For a = (a1, E R² we say that a set of solutions CP, an approximate convex Pareto set if for any solution (C,o) there is convex combination of solutions in CIP, that is an a-approximation to (C, ) In this context we always assume (1) = 02 and therefore just write CPp,, a; instead of (IP(a..a)) 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 finite set P, metrics d1; d2 P and two objectives fi, (med, mean). Let e > O. Then we can compute an (5 + -)approxxmatee convex Pareto set CP8+e in time that is polynomial in the imput size and? where 2.6 2.67059 if f1 med and fz med, and 9 + if ft med and f2 = mean or Ji mean and f2 = mean. The size of this set |CPotel is also polynomial in 1 and |l..
3 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://ggtaiiii com/ algoa aalgo-ahhpprretoouusttrrii
3.1 Application: k-separation and k-means
We test the approach to combine k-separation with conflicting objective. As that second objective, we choose k-means. Since the data sets used in our experiments are from Id, we do not use the algorithm described in Sec. A.3 for general metrics but variant of it which tailored to Rd and allows centers from Rdd instead of only P. It is described below. The Euclidean metric is used for both sep and mean. We test this algorithm the number & of clusters to be the desired number of clusters in the ground truth. All data sets were downloaded from freely available sources, see Table for information on the data sets.
data sets from Rd with available ground truth. We fix
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²) possible values for the separation. We compute these values in time (n²d) and sort them in increasing order in time O(n2 log(n)). Starting with separation 0, we increase the separation in every step to the next largest value. Suppose the separation is A in the current step, then merge all points whose distance is at
8

---

(a) Clustering by k-means++ for (h) Clustering by Single Linkage
(c) Best clustering on the approxi- mate Pareto curve for & 10.
k = 10.
for = 10.
Figure 4: Clusterings computed on data set 2d-10c-no4 by Handl and Knowles 33
Table 5: NMI of the best solutions by single linkage and k-means+++, and of the best solution C* in the Pareto set. Randomized algorithms were repeated 20 times and values are then averages.
Rice
Dry Bean
Wine
Optdigits
Iris
2d-4c-no3
2d- 2d-10c-no3
2d- 2d-10c-no4
SL
0.0007
0.1626
0.0615
0.1220
0.0000
0.4631
0.6763
0.7260
KM++
0.4693
0.5164
0.4265
0.7459
0.7405
0,8715
0,9065
0,9052
C
0.4728
0.5231
0,4400
0.7627
0.8578
0.9267
0.9491
0.9779
most A. This can be done efficiently via a Union Find data structure. Since the resulting clustering may have more than & clusters, we have to reduce the number of clusters to k. For data sets in RR'' 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 al. [46] for general metrics. Instead of choosing the theoretically best approximation algorithm for k-means, we use k-means++ g to cluster the centroids it is fast (running time ((nkd)) and usually produces solutions of high quality for the k-means problem in practice. Then the respective clustering the original data set has separation at least A and at most & clusters. One can show that this algorithm computes an a-approximate Pareto set with a (1, (log k)).
Prototypical desired behavior. Consider Fig. 4 shows the data set id-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 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 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. [8 in the suppl. material). Fig. shows the Pareto curve. The 16th point with separation of 0.68 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 compute the Normalized Mutual Information (NMI), Rand Index (RI), and Fæ-scores for 3 = 0.5, 2. Each of these measures results in values in [0, 1]. where a value of I 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. AA.3 in the supplementary material. Table 5 shows the Normalized Mutual Information Score for all tested data sets. We see the best solution found in 20 runs of the respective algorithm (except for Single Linkage, which is deterministic). The algorithms were run with the associated with the ground truth of the data set. Single Linkage does in general not perform well in recovering the ground truth clustering. The clusterings produced by k-means++ are much better. For all data sets, the NMI the best Pareto solution is even higher, with some notable positive examples like iris and 2d-10c-n4. The other performance measures show similar tendency, although sometimes C' is slightly worse, for example data set rice (see Table [ in Sec. A.3) This can happen because the solutions

---

(a) Purely income based clustering.
(b) The 10-th Pareto solu- tion
(c) Purely geography based
clustering.
Figure 5: Comparison between the 10-th Pareto solution with the purely geographic and the purely income based clustering for k 16.
Table 6: Comparison between the time series based clustering, the geography based clustering, and the 54-th Pareto clustering with regard to the biggest cluster radius for both metries and the mean cluster radius over all clusters for both metrics.
max rad geo
mean rad geoc
max rad ts
mean rad ts
Geography based clustering
1566 km
619 km
20,9
4,1 cm
54-th Pareto Solution Time Series based clustering
2411 km
799 km
8,0 cm
3,1 cm
18172 km
1570 km
6,7 cm
2,8 cm
the Pareto front do not necessarily include the pure k-means++ solution special case because it is only an approximation to the optimal k-means clustering and therefore can dominated by other solutions in the approximate Pareto set with smaller k-means cost.
On all data sets that are not synthetic, the best result in the approximate Pareto set uses small separation value. Therefore we conjecture that it is sufficient to use few steps of single linkage before starting k-means++ in order improve the quality of the solution.
3.2 Applications: k-center with two different metrics
We use two o-center-objecttvvs with different metries 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 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 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 cleaner structure than the purely income based clustering, but the same time shows how the median income behaves in different regions of Germany.
For our second application we use data set that consists (normalized) time series of the 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 d1 we use the mean difference between the time series. As geographic distance measure d2 we use the Euclidean distance between two stations. The time-series-bies based distance and the Euclidean distance of the gauge stations can behave very differently. We cluster with 150. Then the approximate Pareto set contains 106 clusterings. Table shows the maximum and mean radii of the clusters in the solutions computed purely based geometry, in the solution purely based on the some-series-basee distance, and carefully picked Pareto-optimal solution. The numbers show that the Pareto-optimal solution is very reasonable trade-off.
10

---

Acknowledgments and Disclosure of Funding
This work has been funded by the Deutsche Forschungsgemeinscaat (DFG, German Research Foundation) 390685813 and 459420781 and by the Lamarr Institute for Machine Learning and Artificial Intelligence (lamarr-ing iaaurr-insttutt.orga We furthermore thank Johanna Hillebrand for providing code visualize the sea level data.
References
[1] Rice (Cammeo and Osmancik). UCI Machine Learning Repository, 2019.
C5MW4Z
[2] Dry Bean. UCI Machine Learning Repository, 2020.
[3] Stefan Aeberhard and M. Forina. Wine. UCI Machine Learning Repository, 1991. DOI: https://doi.or//10 htt.:/orrg/...452//SPPCC...
[4] Sara Ahmadian, Ashkan Norouzi-Fard Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. Proc. of 58th IEEE Annual Symposium Foundations of Computer Science, (FOCS), pages 61-72, 2017. doi 10. 1109/
FOCS 2017.15
[5] Soroush Alamdari and David B. Shmoys. A bicriteria approximation algorithm for the k-center and k-median problems. Proc. of 15th International Workshop on Approximation and Online Algorithms (WAOA), pages 66-75. Springer, 2017. :oi:
[6] E. Alpaydin and C. Kaynak. Optical Recognition of Handwritten Digits. UCI Machine Learning Repository, 1998. 104::0.24432//05555 (4432/C50049
[7] Alna-Klara GroBwendt. Theoretical Analysis of Hierarchical Clustering and the Shadow Vertex Algorithm. PhD thesis, Rheinische Friedrich- Wilhelms-Univeeee Bonn, May 2020. URL:
https://hdl. handle. nwt.to. 500. 11811/8348
[8] David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proc. of the 18th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 1027-1035, 2007. URL: http://dl.aa
cfmmcdcmmiii.. 1283883. 1283494
[9] Lilian Astrid Bejarano, Helbert E. Espitia, and Carlos E. Montenegro. Clustering analysis for the pareto optimal front in multi-objective optimization. Compul., 10(3):37, 2022. doi N0..339/ccome wwwooottttton00000.coooooo
[10] Ahmed Nasreddine Benaichouche, Hamouche Oulhadj, and Patrick Siarry. Multiobjective improved spatial fuzzy c-means clustering for image segmentation combining pareto-optimal clusters. J. Heuristics, 22(():383 404, 2016. doi: 10.
9267-9
[11] Moritz Buchem, Katja Ettmayr, Hugo K. K. Rosado, and Andreas Wiese. A (3 E)- approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds. In Proc. of the 2024 ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 1738-1765 2024. doi : 10. 1137/1 978 977117711111991111
[12] Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor ap- proximation algorithm for the k-meiaa problem. J. Comput. Syst. Sci., 65(1):129-144 2002. doi: 10. 1ww.0/ocsse.. 2002. 1882
[13] Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. J.
Comput. Syst. Sci., 6872):417-41,, mar 2004, doi : 10. 1016/ JCSS. 2003. 07 .014
[14] Carlos A. Coello Coello and Maximino Salazar Lechuga. MOPSO: proposal for multiple ob- jective particle swarm optimization. In Proc. of the 2002 Congress on Evolutionary Computation (CEC), pages 1051-1056. IEEE, 2002. doi 10. 1 1109/CEC. 10002.0004389
[15] Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Im- proved approximations for euclidean k-means and k-median, via nested quasi-independent sets. In Proc. of 54th Annual ACM Symposium on Theory of Computing (STOC), pages 1621-1628.
ACM, 2022.
doi 10. 1111/111//19931 152011 3520011

---

[16] Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, and Chris Schwiegelshohn. Breach- ing the LMP approximation barrier for facility location with applications to k-median. In Proc. of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 940-986, 2023. doi: 10. 1117/1111111 / 97711119771744 CH37
[17] Vincent Coden-Addad, Karthik C. S., and Fuiwoong Lee. Johnson coverage hypothesis: Inapproximability of k-means and k-median in p-metrics. In Joseph (Seffi Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1493-1530, SIAM, 2022. doi: 1 1 11111111111/11991111117770000000 9781611977073 63
[18] Copernicus Climate Change Service. Climate data store, (2021): Oras5 global ocean reanalysis monthly data from 1958 to present. copernicus climate change service (c3s) climate data store (cds). : 2438144311/ cds. 67e8eeb77
[19] H. William Corley and I. Douglas Moon. Shortest paths in networks with vector weights. Journal of Optimization Theory and Application, 46(1):79-86, 1985. : 1007 1007/BF09933761
[20] lan Davidson and S. S. Ravi. Intractability and clustering with constraints. In Zoubin Ghahra- mani, editor, Proc. of the 24th International Conference Machine Learning (ICML), pages 201-208, 2007. doi 10. http://112349..17733553
[21]
Arbeitsgemeinschaft der Vermessunggswervaauugeen der Länder der Bundesrepublik Deutsch- land (AdV). wttp://httpgerrrropoooaaaaaaaaaa
de/
[22] Ilias Diakonikolas. Approximattion of Multiobjecttive Optimization Problems. PhD thesis, Columbia University, USA, 201 :11:::.:.91:0000.000. /
[23] Matthias Ehrgott.
Multicriteria Optimization (2. ed.). Springer, 2005. doi:10.10077
3-540-27659-2
[24] Katti Faceli, André Carlos Ponce de Leon Ferreira de Carvalho, and Marcílio Car- los Pereira de Souto. Multi-objective clustering ensemble. Int. J. Hybrid In- rell. Syst., 4(3):155-15,, 2007. URL: http:://conttenttoooppeeee htt.://ooooaoaooooooooooiiieeeee
[25]
Tomás Feder and Daniel Greene. Optimal algorithms for approximate clustering. In Proc. of the 20th Annual ACM Symposium on Theory of Computing (S7OC), page 434-444 New York, NY, USA, 1988. Association for Computing Machinery. doi: 11141.0111////2222.222 62255
[26] R. A. Fisher. Iris. UCI Machine Learning Repository, 1988. doi: :0. 24432/C56C76
[27] Ana L. N. Fred and Anil K. Jain. Robust data clustering. In Proc. of the IEEE Computer Society Conference on Computer Vision and Puttern Recognition (CVPR), pages 128-136. IBEE
Computer Society, 2003. doi: 10. 1109/ 2003. 1211462
[28) Zachary Friggstad and Mahya Jamshidian. Improved Polynomial-Timee Time Approximations for Clustering with Minimum Sum of Radii or Diameters. In Proc. of the 30th Annual European PrwpetioiooooPooeinnnnnii
Symposium on Algorithums (ESA), Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1-56:14 14, 2022. doi 10.
[29] Bundesagentur für Arbeit. Sotaaleericherugggffhhiigeg battrraeegeebetttoooreeeeetgeee im re- gionalen vergleich, 2021. URL: http::/://saatiiii...rrrraaaaass de/DE/
Entgelte-regional html
[30] Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 306, 1985. doi: 10.
[31] Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms.
J. Algorithms, (1):228-248) 1999. Utt./h/paee//oo..or//00/00//////
1998 0993
doi: 10. 1006/ JAGM. 1998.0993
[32] Julia Handl and Joshua Knowles. 2d- 10c-no3. URL: httpg//pprroonaapggssnacceeettt
ac. we.uk/staff http://alll.aaamnegeeeetttto.rr httll
[33]
Julia Handl and Joshua Knowles. 20-10c-no4. URL:
ac. wtt.///aaaa//llaaaaaaaa/eeeeeee
[34]
Julia Handl and Joshua Knowles. 2d-4c-n03. URL:
ac. wc.uk/staffs julia. handl/generators..ttt.
12

---

[35] Julia Handl and Joshua D. Knowles. Exploiting the trade-off the benefits of multiple objectives in data clustering. In Proc. of the 3rd International Conference on Evolutionary Multi Criterion Optimization (EMO), pages 547-560, 2005. ( 0-077----------188-----------
[36] Julia Handl and Joshua D. Knowles. An evolutionary approach to multiobjecttive clustering. IEEE Trans. Evol. Comput., 1 11(():56-76, 2007. doi 10. 11w9/ 2006 877146
[37] Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. problem Mathematics of Operations Research, 10(2):180-184, 1985. doi 10. www.11187///o00 10. 180
[38] Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. ACM, 33(3):333-550, may 1986. doi: : 10. 114455525.55933
[39] Simon J. Holgate, Andrew Matthews, Philip L. Woodworth, Lesley J. Rickards, Mark E. Tamisiea, Elizabeth Bradshaw, Peter R. Foden, Kathleen M. Gordon, Svetlana Jevrejeva, and Jeff Pugh. New data systems and products at the permanent service for mean sea level. Journal of Coastal Research, 29:493-504, 2013.
[40] Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discret. Appl. Math., 133):209-213 215, 1979. doi: : 10. 10111016/11100 218X (7)990411
[41] Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the drimal-dual schema and lagrangian relaxation. J. ACM,
48(2):274-266, 2001. doi 10. 1014/1115577... 375845
[42] Abdullah Konak, David W. Coit, and Alice E. Smith. Multi-objecttvv optimization using genetic algorithms: A tutorial. Reliab. Eng. Syst. Saf. 91(9):992-1007, 2006. URL: https
//doi.org/10 1016/j rress. 2005 11. 018 doi: 10. 1016/J116JJ.. RESS. 2005. 118
[43] Bjornar Larsen and Chinatsu Aone. Fast and effective text mining using linear-time document clustering. Usama M. Fayyad, Surajit Chaudhuri, and David Madigan, editors, Proc. of the 5th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 16-22. ACM, 1999. doi : 10.
312186
[44] Euiwoong Lee, Melanie Schmidt, and John Wright, Improved and simplified inapproximability for k-means. Inf. Process. Lett., 120:40-43, 2017. [doi: 10. 1016/J. IPL. 2016 11. 11.009
[45] Nissan Lev-Tov and David Peleg. Polynomial time approximation schemes for base station coverage with minimum total radii. Computer Networks, 47(4):489-501, 2005. doi 10.
j .comnet. 2004. 012
[46] Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. A general approach for incremental approximation and hierarchical clustering. SIAM Journal on Computing, 39(3):3633-366) 2010. :oi: 11.0..1137 /137/070982
[47] Anirban Mukhopadhyay, Ujjwal Maulik, and Sanghamitra Bandyopadhyay. A survey of multiobjectiive evolutionary clustering. ACM Comput. Surv., 47(4):61:1-611 61:46,, 2015. doi
10. 1144//2444642
[48] Adli Mustafa and Mark Goh. Finding integer efficient solutions for bicriteria and tricriteria network flow problems using dinas. Computers & Operations Research, 25(2):139-153 157, 1998.
do 1016/50305- 0548 000270000
[49] Christos H. Papadimitriou and Mihalis Yannakakis. On the approximability of trade-off's and optimal access of web sources. In Proc. of the 41 Annual IEEE Symposium on Foundations of
Computer Science (FOCS), pages 86 66-92, 2000. doi: 10. 1109/SFCS 2000. 892068
[50] Permanent Service for Mean Sea Level (PSMSL). Tide gauge data, retrieved on 13 november 2023. URL: htttp://www... http:///www..ssll..mm wwg. data/ obtaining/
[51] William M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66(336):846 850, 1971. doi: 000:10.10800/011 1011000000119..111111 1971 10482356)
[52] Robin Sibson. SLINK: an optimally efficient algorithm for the single-link cluster method. Comput. J., 16(1):30-33)) 34, 1973. doi: W099/CCMJJLLL 1 1....... 1.30
[53] J. van Rijsbergen. Information Retrieval. Butterworth, 1979.
[54] Silke Wagner and Dorothea Wagner. Comparing clusterings: an overview. Technical report, Uni- versität Karlsruhe, Fakultät für Informatik Karlsruhe, 2007. URL: htttps://publikatiioo
bibliothek. .ww.eeuu//eeeeekkk...... wartt.ed/11000 100001100111
13

---

Supplementary Material
A Theoretical Part: Pareto Sets for Combinations Involving ls-separation
Given set of points P, l E N and metrics d1, d2 P, in the previous sections define k-clustering on P as a set C centers and an assignment Ø: P - C. For combinations involving k-separation, it can be helpful view clusterings partitionings. We introduce the following equivalent notation that used Sections A. A.2.1 and Section A.2.2
Observe that (c) | we observe that this partition is already sufficient to compute the objective values the solution. Let E be partition of P of size k, for i 1,2 define
C} forms a partition of P of size k. The only change in definition is that
min sep(6, .d,) C,C'EE,CYC' PEC.
min d.(p.
diam (8, (d)
max max (p 4)
CE'6 P-gEC
rad d,) max min max d, c).
CC'6 cEC PEC
For convenience we view a k-clustering as partition of P in & clusters in Sections A.1 A.2.1 and Section A.2.2
A.1 Combining k-Separation and k-Separation
We consider the k-separation problem and observe that defining threshold for the separation translates into a set of must-link constraints. We define the graph points that have be connected given a certain separation value and use this to define a clustering.
Definition 2. Let (P,d) d) be finite metric space and T 2 0. The r-separation graph (TP of consists of
vertices V(P,a) P and
edges (T) {1 v} Z.yeP: d(z, ST).
We denote by (P, the clustering consisting of the connected components of (T).
The following shows that ((,d)) is in some sense at the heart of r-separability. For brevity, we use the following in this lemma: We name clustering of P T-separated if S max..Cre....C )ixx d(c,e)).
Lemma 3. Let (P,d) be metric space and 0. Then
1. (T.)((T)) is r-seprrated.
2. If is clustering of (P,d) d) then it is r-separated if and only if (P is a refinement of clustering 6. This means that for every S E ((( there exists some C' 6 such that SCC.
In this sense, (T) can be called the minimally 7-separated clustering.
Proof. This immediately follows from two easy observations:
The minimal distance between two different clusters S, E (P,aa is strictly more than Otherwise edge would have been added between the respective points.
2. We cannot split any cluster S (P(P (T) without lowering to separability at most since S is connected in G(p.a) (T) at least edge would have to be cut.
Lemma Let (P.d) d) be a metric space consisting of n elements, and 2 We can compute I(P (T) in O(n²) time.
14

---

Proof. The r-separation graph can be computed in O(²²) 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))) when we combine fi sep and f2 sep on possibly different metrics d1 and d2. Given two thresholds TI and 72, just compute / = (F((p. .P.44) (TI) and merge all of its clusters S, S" whose distance (".(s d2 d2 at most 72. In other words, we merge S and S", whenever there exists a cluster 5" E E (P(()d))) (T)) with S n S" * Ø and S" nn"" * Ø. The resulting clustering is minimally hierarchically com- patible with both (P,d,) (T1) and ((..d) in the sense that every other clustering hierarchically compatible with the latter has to be compatible with & as well. All merges we have conducted were necessarily forced to achieve the separation values. Had we left out any of them, of the separation values would be violated. We can thus conclude with the following result.
Theorem 5. Let d1, d2 be two metrics defined over a finite set P. Then fi = sep and f2 = sep can compute their Pareto set in polynomial time.
A.2 Combination of (-Diameter/k--Center with k-Separation
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--cnnte, 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 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 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 separate cluster). In fact, if we fix the number of clusters, then there's s no guarantee that a solution that yields constant-factae approximation for both objectives 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 simultaneously constant factor approximation for d-center/k-diamette and k-separation.
Example 6. For any fixed m. E N₂1 consider the set
Pm. (l...., k 11- (- x E (o...., m(k 1)2}}
Am
and the Euclidean metric di (z. v) dz(x, 3)
x yl on R.
We first show that any constant-fact factor approximation for either the k-diameter or the k-separation objective performs poorly for the other objective.
First, note that 66 = {{1)....: {k- - 1}, } the only clustering with separation value of sep(E E, d2) 1. Indeed, any other k-clustering '6' has to break up Am and so has separation of only sep(6", d2) = 11/m (the distance between any two consecutive points in Amd). other words, @ is the only solution that provides
constant-facter approximation for the k-separation objective. However, '6 does not provide a good appreximation for the k-diameter objective. Since it does not break up Am- it has diameter of (k- 1)2. This is worse by factor of k - than just indifferently dividing up Pm into l sets of "equal size". Indeed, partitioning |-(k 1)2 k 3 Pm into intervals of equal length yields clustering of diameter at most
(k: 1)2 (k le(1 -
k
k
The same argument also shows that constant- approximations for the k-diameter objective perform poorly with respect to the k-separation objective. A solution that provides constant-facio approximation for the k-diameter objective has to break up Am and thus has a separation value that is m times worse than the optimal.
15

---

For k-center the argument works analogously with the only difference that the radius of is lower bounded by (k-1)² while the optimal solution with respect k-center has radius at most k-1
2 +
Thus, instead of trying to optimize k-diameterrkk-center and k-separation simultaneously, again focus on Pareto sets.
A.2.1 Combination of B-Diameter with k-Separation
In line with previous sections will provide subroutine that, given estimation of the value of Pareto- Pareto-optimal solution, will compute a close approximation.
Theorem Let S, D diam(6" ,di S D and sep("* .d2) 2 S. then Algorithm [ compules solution E in polynomial time with (iam(6,d) S 2D and sep(6, d2) 2 S. If no such clustering E exists, Algorithm returns an error message.
be two non-negative numbers. If there exists a clustering "6 with
Algorithm| Lis a relatively simple subroutine that, for a pair of possible diameter and separation values, either constructs (1, appproxxiitao in polynomial time, signals that no such Pareto-optime solution exists. Using this subroutine we can simply iterate over all diameter-separation pairs and collect the results to get approximate Pareto set Pa with (1,
Algorithm 1: Approximate solution for k-diameter and k-separation
input :A finite set P, two metrics d1, d2 on P, number k N, two values D, R22-
8 t {x) P) while 30, E E C d²(C,C)) < do
8 + (8 (1,11CC))UCCCC)
< diam(", di) or [6| then
L return no such clustering exists
GeD + (6, ([C, C"} diam(C di) S D))
I (I,...., [e] maximal independent set in GgD
8 i > 1: then
L return such clustering exists
10 partition Gen into star-graphs Si.... St centered around 4
11 forall E [1....,)] do
12
D
0
13
forall C E S, do
if |6] k then
15
return 66
8 - ( (8 (D)) D - DUC
16
17
18
return C
Before proving Theorem we will quickly outline Algorithm [ splitting it into two phases. In the first phase (we could also call it the we successively merge those that have distance less than S with regard d2. This is necessary to ensure a good separation value. In the second phase (we could call this the Hochbaum-Shmoo phase) we then reduce the number of clusters further, while ensuring that the diameter with regards to d, does not grow too large.
phase), starting with [P] clusters of size one each,
Proof of Theorem 7 Let us first consider what happens when Algorithm message. Clearly, this only happens when reach line or line 9 In any either case, have to show that there cannot exist a clustering E with diam " d,) I and sep("6", ( show that the assumption that such clustering 8* exists yields contradiction.
T fails and returns an errоr
We
Consider the first case where Algorithm T reaches line 5 In lines T to 3 we have, starting with separate cluster for each point, merged all clusters that a distance of at most S from each other.
16

---

(Apart from the order in which the clusters get merged. this is the same as running the Single Linkage algorithm on (P. d2).) Note, that clustering 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; E P. contained in different clusters, with d2(x, y) < S. In other words, to ensure separation value of at least 8, every merge performed so far has been obligatory and so, if we reach line 5] we know that "6" cannot exist.
Next, consider the other case in which Algorithm [ 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 graph G&D in lines in this graph represent the only merges that could in fact be made without violating the requirements imposed on E They represent the only merges whose resulting clusters have a diameter of at most D. Now, once we reach line we know that this graph contains an independent set I of size > As outlined above, all merges so far have been obligatory and so it follows that for each C' E g there exists some C* E 66" with C' [ C". Therefore, by the pigeonhole principle there has to be a cluster C* that contains two different clusters from V. But I is independent set in G&D and so diam( (8, di) 2 diam(C* di) > D. Again " with the desired properties does not exist. This concludes the first part of the proof.
whose edges indicate viable and cheap merges. That is, edges
What's ' left to show is that, whenever Algorithm I returns a clustering, in fact returns a good clustering. In the first phase we have constructed a clustering '6" with sep("6", d2) 2 S and diam(6 d1) S D. but potentially |66]] k. By subsequently merging clusters within star-graphs induced by an independent set within GgD, 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 straight-forward application of the triangle inequality: every star-gree star-graph clearly has a diameter of at most 2D.
Corollary 8. Given a finite set P and metrics d1, d2 on P. We can compute the approximate Pareto set Pa for a = (1,2) with respect to the objectives f1 sep and f2 = diam in polynomial time.
Running Algorithm| [ with a separation value of S = 0 (or S < min{d2
+ P))
amounts to finding a 2-approximate solution for the standard k- k-diameter problem. Since it is known that there does not exist a polynomial-time (2 -)-aprooximation algorithm for this problem, unless NP 25), we know that the (1, 2) -fctor established Theorem 7 cannot be improved.
A.2.2 Combination of k--enter with k-Separation
We can also combine the k-separation objective function with the kt-center objective function. Since the latter 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 [ has to be adjusted to ensure that the following theorem, analogous to Theorem 7, holds.
Theorem 9. Let S, R. R be non-negative numbers. If there exists k-center solution E- with rad(" di) < R and sep(6" d2) Z S. then Algorithm 2 computes a solution '6 in polynomial time with rad(6, dd) S 2R and sep(" E6 d2) '2 S. If such clustering 6" exists, Algorithm returns an error message.
Algorithm 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 6 satisfying the bounds in the theorem leads contradiction. The first
case, where Algorithm 2 return an error message at line 5|ann be handled in exactly the same way as in the original proof and so we won't repeat here. Instead, consider the case, where Algorithm [] returns an eтror message in line [ 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 &6 is in fact just refinement of the clustering 8*, which means that there have to exist two clusters C, C' E I that are both subsets of the same cluster C* E 66" But then C* has to have radius of rad( C* d1) ddiam(C C") > R. contradicting assumptions.
17

---

Algorithm 2: Approximate solution for k-center and k-separation
input :A finite set P. two metrics d1, d2 P, number & N, two values R E R R20-
6 (rEP)
2 while 1C,
C d2(C.C") do
6 + (6 (VV1CCCT)u(CCC)
it R < rad(66, or [6] < k then
L return no such clustering exists
Geen t- (6, ((C,C")) } | diam(C d1) S 22))
7 I (1,....,44) [t) <- maximal independent set in Gg2n
if k: then
return such clustering exists
10 partition G22R into star-graphs SI.... centered around 4,... d
forall E {1, (I....,{. do
12
D = /
13
forall C E S; do
14
if | = h then
15
return 6
6 8 ( ((DD)) DUC
17
18 return E
Finally, we prove that any clustering returned by the algorithm is in fact good solution. That the lower bound for the separation value satisfied is, again, obvious. Let us thus move on to the the upper bound the radius. After the first phase all clusters necessarily have radius of most R (otherwise the algorithm would fail in line 5). To see that the second phase does not increase the radius by much, fix 2ι E for every cluster I E I For every 1 E I all other clusters C belonging to the star graph of I are close to / in the sense that diam C)) S 2R. In particular di (2(2,,2) x) 2R for all x E C, implying that, indeed, rad(Uces C) 2R.
Corollary 10. Given a finite P and metrics d1, d2 on P. We compute the approximate Pareto ser P.. for a (1,2) with respect to the objectives fi = sep and f2 = rad in polynomial time.
Again, the (1, 2)- approximation factor cannot be improved. For S 0, Algorithm 2 computes 2- approximate solutions for k-center, which is the lowest approximation ratio achievable in polynomial time 388, unless P = NP.
A.3
Combination of k-separation and i-median/k-means
The instance outlined in Example 6 can again be used show that there is no hope of finding clustering that performs well with regard to both the k-median (or k-means) and the k-separation objective.
Observation 11. Consider set of points fz/m x E fo,.... m.))) ) for any e and The 1-median cost of this sel is given by
mf
l
2
nnf
ml
2
m
m
m
0=0
mnt
2
Σ r
{(ml + +2)
m x=1
4
since the points are evenly spaced and thus the optimal center f/2. Now, if we consider the same set
P Pk.m
{-x/m// x E (0, .., m(k 1)2 Ufl..... k-1) 1)
Aq.m
18

---

as in Example 66 then we run into the same issues. By the above computation, Ag.m has I-median cost that is in ( whereas the subsets that we get from dividing [-(k 1alk-11- 1)², k-1] into k intervals of equal length each have a I-median cost that is in O(k2). The k-median cost of the only clustering '6 = =[()...... {k=- 1}, Ag.m that achieves a constant-factor approximation ratio with regard to
sep worse by factor of (Q(k) than that of the optimum. Conversely, if we split up Ak.m to achieve a good k-median solution, then the separation value will be bad.
Thus, before, we have shown that all clusterings can have good (i.e. constant-facton approxima- tion 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 PP we know that for the same reasons the Pareto set for this combination consists of at most n(x-1) different solutions.
Theorem 12. Given a finite set P. two metrics d1,d2 and objectives fi sep and f2 med. Then we can compute the a-approximate Pareto set P., for a = (1,2 + 5) with respect to fı, I2 in polynomial time, where 8 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 (2.67059 - >)approximatioon algorithm for the k-median problem.
Corollary 13. We can compute the approximate Pareto set P. for = (1, 4.67059 + c) with respect to the objectives fi = sep and f2 = 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 fi E {med, mean] admits the (r, o)-nesting property if the following holds for every clustering instance. Let P be a finite set of points, a metric on P and k N. For every two clusterings (C, σ), (C', , o') with |C| k and |C"| > k there exists a clustering (C,ō) with |C| = k which satisfies the following properties
for p.q E P with o' (p) = (4) we have T(p) = a(g) and 2. med(ū, G. S y mCd dd) + med a, d). We call (Č,6) (7, -)-nstin 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 k-median admits the (2, 1) -nesting property. For k-means in the Euclidean space GroBwendt 7 shows that k-means admits the (4, n)essingg property.
For k-median we follow the approach for the (2, nnesting by Lin et al. 46 to compute the approximate Pareto set P(1.2+5) with respect to fi = sep and f2 = med.
Lemma 15 (16)). The k-median objective admits the (2, 1e-ssting property.
Proof. Let P be a finite set of points, d metric on P and k E N. Given two clusterings (C, o) and (C", with |C| = k and |C'| >> le we want to construct clustering (C, 7) which is (2, 1-nesting with respect to solutions (C, o) and (C",o')
We now construct our solution by setting Ō C. For p E P we define the assignment as follows
(p)) argmin d(c, (p)).
Now notice that (Õ, ō) satisfies [ = Furthermore we have for points p,q E P with o'()) = o'(1) that T(p) T(g).
19

---

To bound the k-median cost, we first bound the distance of each point to its center:
d(p. T()) - d(p, o' (')) (()((p),((p))
s d (p)) + d(o' d d(p,
2 (p)) d(p,
The first inequality holds due to the triangle inequality. The second inequality holds due to
d(o' (p), a()) = min d(o' (p). c) S (p), (p). I ((o'(p)))) +(pp (()).
cEC
Taking the sum over all points gives us:
Σ
d(p.T(p)) = E d(p, (p)) + o(p.
PEP
PEP
med((", , o' d) (e, dd)
This concludes the proof.
We now apply this lemma to compute the approximate Pareto set for fi = -ee and f2 = med.
Lemma 16. Given the minimal distance between two clusters > 0. Let (C", o²) be the optimal k-median solution with respect to d2 that fulfills sep(C*, ,=,di") ,'""C"""',,"
D. Then we can compute solution (C, o) with [C] = k such that all clusters have at least distance D to each other with respect d1, and (ed o, d2) (2 + 6) med o² .d2) in polynomial time or report that there is no such clustering.
Proof. Since we have given the minimal distance between clusters D, know that all points that have distance smaller than D to each other must lie in the same cluster of (C*,a")). Therefore we can construct a clustering (Cs, og) that greedily clusters all of these points together.
Note that there exists a solution that fulfills our distance requirement then |Csl 2 k since all of these groups would have be present in (C*,o") which is k-clustering. If not, then D is chosen too large.
If |Csl k. then it must hold that (Cs. = (C",o") and we are done. Therefore we assume for the rest of the proof that [Csl > k.
is clear that all points that are clustered together in (Cs, must be clustered together in our solution (C) because if there are points p. q with sp = o5(g) but app) * a(q) we have (p g) < D and therefore sep(C, o) < D. Therefore the solution (C,a) must be compatible with (Cs, os) and the same time ensure that the k-median cost with respect to d2 is not too high. To ensure this, we denote by (CM, aM) a ò-approximation to the best k-median solution (w.r.t. d2). Therefore (CM, MM) also a 5-approximation to (C*.a*).
Since the separation cost function is independent of the set of centers Cs we can without loss of generality choose the center which are in the same cluster in (Cs, as) have to be in the same cluster (C*, oa) as well, we know
be the set of points that minimizes (es, Js, d2). Since points
med(C's, as, d2) < med(C", "0"C""""",,," ,o,
Now let (C,o) be a clustering which is a (2, 1) -nesting with respect to (M). and (Cs, as). Such clustering exists by Lemma 15
For all p.g g with di (p. q) < D holds that (p))) (g) and therefore also (p) (g). Thus we obtain sep(C, di) Z D. For the k-median cost with respect to da we obtain
med (C, a, d2) < 2 med(Cs, (Cs,as, d2) + med(Cas, a., < 2 (ed ,0",,"",""" ,o",d2) + med(C", ,a",22)
= (2 + 5) med(C", 00" dd2).
where the last inequality holds because of inequality I This concludes the proof.
20

---

The theorem now follows from the fact that there are only n(x-1) 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 [6] we say (Cd, d2) I 8. med(C" ,d2). The same guarantee holds also with the optimal k-median clustering instead of the Pareto-optimal solution (C",,") o²), and in cases where the Pareto-optimal solution has bad values for the k-median target function, this might be 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.
Theorem 17. Given a finite set P and two metrics d1, d2 and objectives fi sep and fz mean.
Then we can compute the a-upproximate Pareto set Pa for = (1,4 4 + 4 vō + 8) with respect to Jt, f2 in polynomial time, where ó the best approximation bound achievable for the k-means problem with respect to d2-
The following corollary follows directly from the above theorem and the fact that Ahmadian et al. presented (9 + <)-approximation algorithm for the k-means problem in general metries.
Corollary 18. We can compute the approximate Pareto set P. for a (1, + c) with respect to the objectives fi = sep and f2 mean in polynomial time.
We now follow the approach that Lin et al. 46 used to get (8, 2)-nesting, but without setting T 2 the end of the proof, which leads to the following more general statement:
Lemma 19
46
The k-means objective admits the (4, # -nexting property for all T >
Proof. Analogously to the proof of Lemma 15 we get:
d(p, Kp,ā(p))² s (2 (1)
= 4 d(p, o' (p)) +4 d(p, o' (p)) a())) + d(p, a()))
4
$ (4 + d(p, (p)) + (1 7) d(p, (p))
for all >> O. The last incquality follows from the fact that 4ab < T² a² + $ 6² for all a, a, 0.
Summing up over all points leads to:
Σ dd (1)))())) & Σ (4+ d(p (p)) + (1+ + 72) d(p, d(p.o(p))
PEP
pEP
(4 + 72) mea (1 - o,,
In the following lemma, we can now choose the value of 7 in relation to the available k-means approximation factor ó in order to improve our approximation factor.
Lemma 20. Given the minimal distance between two clusters > O. Let (C*, (C*,a") be the optimal k-means solution with respect to d2 that fulfills sep(C",, ,,", d1) > D. Then can compute solution (C, o) with [C| = l such that all clusters have at least distance D to each other with respect to dj, and mean(C, (C,a, d2) S (4 4 +6 me ,d) in polynomial time or report there no such clustering.
Proof. Both the algorithm and the analysis for sep """,""",,,"""""""""""" ,²,di) (1)2 2 D works exactly as in the proof of Lemma 16 Let (CM, xx) and (Cs, as) be defined analogously the proof of Lemma 16
Let (C,o) be clustering which is (4 2 1 + 3/ )nesttng with respect to (CM, and
(Cs, rs). Such clustering exists by setting -² 2 in Lemma 19
For all p, y with di (p. q) < holds that as()) = as (g) and therefore also (p) = =()). Thus we obtain Sep(C, di) 2 D.
21

---

For the k-means cost with respect to d2 we obtain
2
mean o, d2) - (4 2v0) mean(Cs. + +L+ meannC RM d2)
vō
2
I (4 + 2v5) oa" + +5(1= +
mean (",, oa"
v8
= (4 + 2V6) mC 0², ,2) + (6 + 2 2v0) mean( ,0", .2))
= (4 + 4v0 + 5) mean (*,, (2,2))
where the last inequality holds because (CM, is a solution. This concludes the proof.
a ô-approximation to the optimal k-means
A.4 Combining the k-MSR problem and k-Separation problem
In this section, we combine the k-separation and the k-msr objectives. Notice that we here allow that clusterings have less than & 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 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 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. [II) and show that 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.
provide does not turn out to be bad as the ones given in Example or Example [7 This 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
Observation 21. The example that
C (-I
Ak.
with one that evenly partitions Pk.m as a subset (- 1)2 1)2, -1] into l sets of equal length k: - 1, to deduce that C, which is the only constant-factor approximation with regard the k-separation objective, is only ((k) -pprroxxiimta 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 (2k2). In other words, this example does not show that C 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 points, where all edges have weight 1;
2. a clique consisting of k - points, where all edges have weight Vkc
Each distance d(x, y) on the union of both graphs is given as the weight of shortest path between and y. For there to always exist such a path we can just add single edge somewhere between the first and the second part with arbitrarily large weight. Now let us consider the only constant-faets 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 Vh, whereas every other clustering has to have separation value of I because has to split up the line graph. However, the k-msr cost of this solution is [ which worse by a factor of / than merging the clique and leaving each point in the line gruph separate, as the latter has a k-msr cost of exactly Vl.
2
With this established, let us find a convenient formulation of the k-mim-sun sumi--sum-radii problem to be used in this section. We first recall the notion of balls around points.
22

---

Definition 22. Let (P, d) be a finite metric space. For pair (c,r) E P x R, let a( (c, r) {o E P d(z, e) S denote the set of points in P that are at distance at most r from c.
In the introduction, we said that the solution of an instance (P,d) of the k-mst problem is an assignment function P -> C from P to subset C' C P that consists of & centers. The stated goal was to find a that minimizes Eeec max da,,, c). Since the cost of a single cluster determined only by two points, we can conceptualize solutions slightly differently. Instead of an assignment we are looking for pairs (ci.ri)..... (Ce, r3) E x R that minimize E; ry and that guarantee that P S U, B (P..a) (ca, ri). Each such pair induces (not necessarily unique) assignment by mapping each point z E P to a center with d(z,c) (4) S Tt. We will work with this formulation in the remainder of this section. The following shows how we wish combine the k-separation and k-msr objective functions.
Definition 23 (The r-separated k-msr problem). Let d1, d2 be two metrics over a finite set P, k E N, and 2 0. The goal in the r-separated k-msr problem find i pairs P (((1, (Ck, rk)) that minimize cost P) = Ex=1 Ti and that guarantee that for all S E ((P,,,)(T) there exists some is (1....,k) with C ((P,d)) (Cigs Tig)-
Instead of starting with individual points, compute the minimally r-separated clustering in preprocessing step and then only subsequently merge clusters in this clustering to reach clusters. By slightly adjusting the approach by Buchem et al. [T] we get the following result.
Theorem 24. There exists a (3 + -aapproxiimttion algorithm for the T-separated k-msr problem that runs in n (11/e) 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 essential observation established by Buchem et
Definition 25. Let (P.d) d) be a finite metric space and Q C CPP x R a finite set of pairs. The intersection-gras grrpiihonggpphhooo G(p,a) Q) of Q consists of
vertices (( (Q) = Q and
edges a( Q) = ([(e,))
B(P,a) (c, | ()BB((P))) (d', r') + 0}.
One of the most interesting properties of the k-msr objective is that the cost of a solution can some- times be reduced by merging clusters (which cannot happen with the other center-based objectives). For example, this is the case whenever e; E Br,,d) (g,, rj), i.e., when the center of one pair is contained within the ball of another pair. The following result of Buchem al. shows that we can merge sets of intersecting clusters without introducing too much additional cost.
Lemma 26 (Cf. Appendix C of [T]. Let (P, d) be a finite metric space, Q Q x R a finite set of pairs whose intersection-gruyy grapph G(p ay (2) is connected, and T o( an independent set that E r d(P x P) such that
maximizes E(oreer r. Then there exists pair (c",r")
1. Ulerse B(p,a) (c. r) B(p,aj (c", r*) and 2. X* <3
The proof of this result is dispersed over several technical results contained in Appendix C of (m]. Since it does not concern our new constraints, we won't 't repeat it here. However, with this taken care of, we now in the position to work through the actual primal-dual algorithm. Fix arbitrary instance (a finite set P. two metrics dj and d2 over P. a number & e N, a threshold r 2 0) and let (ct, rf)...... (ct rf) denote the pairs of optimal solution P for the 7-separated k-msr problem in non-increasing order of their radii.
The first step is common to all primal-dual approaches for the k-mst problem ( consists of guessing the 1/s largest pairs (ci, ri........ (ci)e: ri/c)) of the optimal solution (where
28 and
we assume w.l.o.g. that 1/s E N). This can be done in n ((1/e) time and leaves us to only have to approximate the remaining k' = k 1/s pairs "i/).............. (ct, rf). The pairs comprising the optimal solution can be of drastically different size, but this segmentation ensures that all leftover
23

---

clusters
The overall approach is the same for us, but we have modify the invariant ensure that the clusters S E Sd 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 P' is contained within the respective ball B ((P.ds) (Ir, 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 g'. But this can easily be rectified by successively increasing the a 's for clusters S; that are not yet covered 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 Or 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 Lt, then we cannot increase both of them, as this would (quickly) lead violation of the respective constraint. Like Buchem al. greedily choose maximal set of aj 's in such J' I' ((Pa))))))))))))))))) |Wi (1,....1//8) 1/6]: g ((p.a,) (c,, rz)]
can be covered by balls of radii at most 11/e S E co). This will give us some breathing room later on. From now on we can focus on the r-separated l -msr problem for P Use 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,, are always covered as a whole.
Primal LP:
minimize
Eier)" r I(c.r)
subject to
E(ar)ss anile, F(ar)
Vj (1.....
WIAN
E(er) F(ar)
F(arr)
where we have a variable o(er)) for every pair (c,r) consisting a center e E P and radius r E = {d(z, v) x. E P: d(a, v) S r. The corresponding dual LP is as follows:
Dual LP:
maximize
Ej aj -
subject
Ej SyCBra O3
r+
V(Gr) (1........
4
0
0
As expected, the second step consists of computing a solution for the dual LP that can almost fully pay for a solution of the original 7-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 [33, as well as Friggstad and Jamshidian (28
Definition 27. Let (ax, A) be a solution for the dual LP and =
A pair (c,r) E P Ris almost tight, if the corresponding dual constraint is fight up to an additive factor of μ., iee,, if
ri/e
[
Σ
aj aj f m.
j: S,CB
Starting with the trivial solution 01 = ... =.. the values in such a way that the number of connected components of the intersection-gran 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't able derive good solution for the k'mmsr problem on P' with the help of Lemma 26
and Buchem al. successively increase
24

---

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 It almost tight becomes tight. Due to the choice of the oj 's, the validity of the solution is guaranteed and the invariant satisfied. As long as the intersection-gran grapihh of the updated set T contains strictly more than k' connected components, we will increase the a 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 riz of the primal LP, Buchem et al. prove that the number of possible iterations is upper bounded by O (IPI') (or rather O (x(PI))). 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 et al. have done (see the proof of Lemma 2.3 in [1]).
By considering all thresholds 7 E dP x P) we get the following result on the Pareto set for fi sep and f2 msr.
Theorem 28. Let d1, d2 be two metrics defined over finite set P and E > 0. Then for f1 = sep and f2 msr we can compute an a-approximate Pareto set Pa with a (L,3 + E) in O (c//e) time.
B Theoretical Part: Pareto Sets for Combining Minimization Objectives
B.1
Combination of two k-center/k-diammter objectives
We will calculate a (2, -aaprooximetee Pareto set for the combination of two objectives S1, f2 (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 Let R = R1 x R2, where R2 = {d,(v, w) e, w E P). For any pair of distances (R1, R2) let GR. Ro denote the graph containing
given two metries d1, d2 on P and want to minimize fa with respect to d;-
edge between exactly those pairs of nodes v, w,w E P fulfilling that di (v, w) < Rí and dz w) < Rz. We adjust the algorithm by Hochbaum and Shmoys [37] as follows. Let 3. 1 if ft diam and B, 2 if fa rad throughout the remainder of this section. As in the original algorithm we can use the graph G Ra. R2. to test for a pair of distances
(R1, R2) E R whether there exists a solution with cost (2R,, 2R₂) or decide that there no solution with cost (R1, R2).
Lemma 29. If the gruph G R2 R2 contains an independent set of size greater than k then there does not exist solution with cost at most (Ri, R2).
Proof. Let us assume that there exists a solution (C, a) with cost (R1, R2). Let v. E P with (v)) = a (w). Observe that d,(v, w) < 2R, if fa = rad and di(v, w) < R. if fi diam and thus v, w are connected by an edge in G R Let / be an independent set in G R2,92 Rg- By the previous observation we know that I cannot contain two points v, w with (v)) = a (w) and therefore
[4] < [C| = k.
O
Lemma 30, GfG R2 contains a maximal independent set I of size at most k, there exists solution (C,o) with C' = and cost at most (2R1, 2R2)).
Proof. For every node we can simply set (o)) = u if E I or (v) for neighbor e of in I (there always exists such a neighbor because otherwise I would not be maximal). If f. = rad it holds that d, (p, a (p)) < 2R, and thus rad(L, o, d.) < 2R, If f. = diam it holds for p, q E with (p)) = (g) that (p, g) < 2R, and thus diam(1, a, d4) < 2R,
Now let R² be defined as the biggest distance with respect to d, smaller or equal than 3,R, between a pair of points in P. Observe that actually G3, Ri Ro = GR. Thus we obtain the following corollary of Lemma 29
Corollary 31. Let R² (. R. di q) fo. 1,2. If G GR.,,, contains indepen- dent set of size greater k then there exists no solution with cost at most (R,, R2).
25

---

In conclusion it is sufficient to compute maximal independent set in .R.,R, for all (R1, E R R1 R₂ (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 R2 contains (n²²) distances between points in P and the calculation of maximal independent set in (n²)) we can compute the approximate Pareto set time (n²)). 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 GR,,R, we do not have to consider any combination (RG, R2)) with R2 < Rr Similarly if the maximal independent set has size most one does not need to consider any combination (Ri. R2)) with R3 > R2 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 R1 E R1 and the smallest distance R2 E R2 and increase the R2 the maximal independent set computed in Gn,,ng has size > k: we decrease R₁ otherwise. This way one would still obtain (2, 2aaapproximate Pareto set while reducing the number of considered pairs in R from (n)") to (n²)) which yields a total running time of (nn)).
This can be further improved by observing the following. If we already have calculated the graph GRa,Rt 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 R1 (and thus remove edges from the graph) or slightly increase Rg (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 E P the set Bр 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²).
Algorithm 3:
sort distances di (p. for p. 9 E P: d S... mm)
sort distances (p for p. E P: d2 .... < d m)
3 let j = 0, (2.2) = 0,
= R = =d1" (m)) R₂ =
let B, = for all pllper P for i m...... ..... 1..,o0 do
while /| > 1e and j < m do
j
R2
dbe d2=
foreach point pair fp, 93 with de(p.9) R2 and di (p. g) s Rı do
10
L ADDEDGE (p.9)
it < k then
12
let 1, let (p) = for E I and (p) = q where g is an arbitrary element in B, for p PEPI P.I. Add (C, to ((222
13
foreach point pair p.g q with dj (p.q) = R₁ and dz 9) _ R2 do
14
REMOVEEDGE L
R d(
16 return P(2.2)
Lemma 32. The following invariants are true for Algorithm (at the beginning of line 6):
1. (P, E) == =GR,Rg
2. 1 is a maximal independent set of G RR,
3. For all p E P, it holds that Bp is the set of neighbors of p contained in T.
The invariant can be proven via straightforward induction. The main idea is, that if we remove an edge between point p in the independent set and another point g need to check whether has
26

---

Algorithm 4: ADDEDGE((P.) (p. 9))
W.I.ogg E + PEl
p E then
L B B (p)
p 1 then
I= ({4) {4}
for r do
B, B, {g)
if Br = 0 then
T= TU (rr
10
Add to B, for all neighbors of
E = E (1p.9))
Algorithm 5: REMOVEEDGE( (p. 9))
E ((p.)}}
if p E T or E then
set V = p.W- p- qi
set v = q, w = otherwise
B. B, {w}
B. 0
I= TU {w}
foreach neighbor r do
B, B, U {v}
still neighbors in the independent set left (i.e. Bg * 0). If this is not the case we need to add to the independent set keep maximal.
If we add an edge, the only critical case appears when it connects two nodes which are both in the independent set. If this is the case, need to remove one of them from keep it independent set. However if we remove we need to check for every neighbor if it can now be added to (i.e., the respective set B, is empty) to ensure that stays maximal. In both operations the entries BN are updated for all x E P accordingly.
Theorem 33. Algorithm calculates a (2, 2) approximate Pareto set.
Proof. Let us consider an arbitrary solution S with cost R2 with respect to ft for = 1,2. We choose f'.j" such that df maxp.gePsti (p-9)) R; d1(p, q) and d(3") paxp.gEE:ddnnnnn R; d2(p. q). Using Corollary we may conclude that if Algorithm reaches an iteration with i' and j = j the maximal independent set has size at most k. By Lemma 30 this results in solution with cost (2R). 2R;) which added to ((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 = = S j" and gets decreased.
One might note that only gets decreased if an independent set of size at most has been found in G dfth -a Since d( < R and d(6 < dgl") < 3, we obtain by Lemma 30 that solution with cost (2R; 2R2) has been found. Thus S is (2, 2) approximated
Case 2: At some point during the execution of the algorithm i 1', increased.
and gets
We observe that j gets only increased if the current independent set / of the algorithm has size greater Furthermore the edge set G (0 ayy) is subset of the one of Gg Goo a()
27

---

Thus I is also an independent set of G 100 d0 However by Corollary 31 this means that there cannot exist a solution with cost (R2 R2)) which is contradiction.
Thus we may conclude that any solution is at least 222)))apppximmacc by one of the solution contained in (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 F and the independent set I of the algorithm. We define (P, E), T) = Eper 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 Bp 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 Bg. We will now bound both the cost of the operation REMOVEEDDE( (p: 9) ) as well as those of ADDEDGE (p. g) by a function in (m) plus the respective potential change A induced by this change (which might be negative).
Before doing this we need to clarify how the sets (Bp) are actually represented by the algorithm. We want to be able add a point By. delete a point and extract an arbitrary element contained in Bp in time (1) each. All these requirements are fulfilled by doubly linked list if we maintain pointers for each edge e = {p. q} telling us where p is stored in the set Bg and vice versa. Using this we can now bound the cost of the respective operations.
Lemma 34. The cost of REMOVEEDGG (v. q}) is bounded by O(2 + A4).
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. be contained in / (note that not both nodes can contained since they were connected by an edge). We distinguish two cases:
If has another neighbor in / besides p. i.e. BBy 2 2, then the size of B3 decreases by 1 and the potential & also decreases by Thus ( A O(1) while the operation takes only constant time.
If p the only neighbor of q that contained in the independent set, q gets added to I as well to ensure that is maximal. As a result for every neighbor of we need to add to B, which leads to running time of (c)), where is the number of neighbors of q, after the edge {p, 9) has been removed. At the same time every neighbor of also increases the potential & by one when gets added to I. Thus A
As result the running time of the operation lies still within
O(2 + 4)= = O(c 1).
Lemma 35. The cost of ADDEDGE(12) (fp. is bounded by 0(2n + AT)
Proof. The only critical case is that both p and q are contained in because otherwise we only incur constant cost while also the potential only changes by constant. In this case the node gets removed from the independent set which means that for every neighbor r we need remove g from B,. 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 we need to add to I to ensure that / is maximal. As result we again need to update the set B, for all neighbors of which costs (deg(r)) while the potential gets increased by deg(r). In total we get that the cost of ADDEDGE bounded by O (n +rEer deg(r)), where I' denotes the set of nodes newly added to the independent set. At the same time:
(0(n+)))
O(2n + AA = 0
2n - n Σ Edeg(r) =0 + Σ deg(r)
rET
rEr
Thus the lemma holds.
Using these two lemmas we can now bound the running time of Algorithm Theorem 36. The running time of Algorithm lies within Onn)).
Proof. The rumning time of the algorithm mainly consists of three parts:
28

---

The sorting of the distances in the beginning which needs time On log(n))
Up to "(x=1) calls of DELETEEDGE and ADDEDGE each (as each point pair gets inserted and deleted most once). Using the previous two lemmas we can bound the respective costs by ( + AΦ) and (2n + A 2 One might note that both at the beginning as well at the end of the algorithm there is not single edge in the edge which means that Φb O. Thus the total change of the potential is O and we can bound the total cost of the insertion and delction operations by (nn)).
2
Constructing solution from the independent set costs at most O(n) since we only have extract an element of Bp for every point E PP. Since at most ((n²) solutions get added to (2.22) (one for every in line line5oof Algorithm 3 the total time for constructing the solutions lies in (n²))
Thus also the entire running time is bounded by (
The following corollary is immediate consequence of Theorem 33 and Theorem 36
Corollary 37. Given a set P of n points, two metrics d1, d2 on P. lo E N and two objectives f1 E frad, diam). We can compute the approximate Pareto set ((2.2) with respect to fix fz in time (n")).
B.2 The size of the Pareto set
In this section we will prove that there can actually exist 22(2²) different Pareto optimal solutions if we combine two different k-center/k -eetmer/-ddiameter objectives with each other.
Lemma 38. For every n E N and f1, f2 frad, diam} there exist set of points P and metrics di, d2 on P such that the size of the Pareto set P with respect to fi, f2 is in ((n²).
Proof. Let be set of size n. We chose the metries d1, d2 on P follows. Let Pl, Pm be all pairs of distinct points in (i.e. m = m(n-1), ). For every i we set di (p:) to 1 m
1 and (p:) to
2 Furthermore we set d1 (p. p)) = d2(p, p) = 0 for all E P. One may note that the distance between two distinet points lies always between 1 and 2. Thus the triangle inequality is trivially fulfilled and d1, d2 are indeed metrics on P.
Now we consider the situation were we want to compute k-clustering with k = 1. Observe that only a single point gets assigned to a center besides itself. Then every k-clustering corresponds to one pair p; of points that contained in the same cluster and vice versa. The cost of this solution (dl (pt), d2 (p:)). It is easy to observe that each of theses solutions is in fact Pareto optimal. Let p; and Pj be two pairs and assume w.l.o.g that i < j. Then it holds that di (p,) < di (pz) while d2 (px) ) > dz(p) which means that neither solution dominates the other one. Thus we end up with m E ((n²) different Pareto optimal solutions.
However one might note, that in the clustering instance constructed prove Lemma 38 many solutions differ only by a small factor. One could obtain a (2, -ppprooxiee Pareto set of size 1 by just choosing arbitrary solution. While this is of course special case one can prove that in fact there always exists (2, apppprooeee Pareto set of size n. This result is direct consequence of the fact that in metric there can only be limited number of distances between point pairs (which correspond to potential d-center/k-diameter 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 PL: ... Pn. in P such that for all + j holds that d(p.) < dd(p,) d(pi) 2d(p;).
Proof. Suppose the statement would be wrong. Then there exists a subset of indices i,, in such that p., {E,, Wt, .... Pse {Uag Whe and w,, Uky+= for all 1,..., 1 and w., u.,- Let w.l.o.g. the distance of p., be maximum among distances of all Pt, Then holds by the triangle inequality that
d(pi,)
d(pi.) ).
2=
29

---

We might observe that the second longest edge is at most half as long as ps, and that the third longest edge is most half long as the second longest and so on. Thus we obtain
k
d(p;,) - d(pi))
Σ ;=1
< d(pi,).
29
which is a contradiction.
The following corollary is consequence of Lemma 39
Corollary 40. Given set P of n points, two metrics d1, d2 P, k E N and two objectives f1 E {rad, diam). There exist a (2, 2)-pprooxmette Pureto set with respect to Ji, f1,12 size O(n).
approxximae Pareto set Q of IP. We will do this by iterating through P.. First let Q = 0. We start by adding the solution that optimizes fi to Q. Then we move along the curve by improving f2 while getting worse in fi- Whenever we encounter solution that is not (222)-approximated by the previous points in Q, we add it. We repeat this until we reach the end of the curve.
Proof. Let IP be the Pareto set induced by f1. f2. We will now construct
Let x and y be two neighboring solutions in Q. Without loss of generality we assume that æ was added Q before y. Note that since we only get worse in we know that fi fix) < fi [v() and therefore it must hold that (u( < f1((x) since otherwise x would (2.2)-aprroximate y.
By construction Q is -aproappooo Pareto set to P. Now assume for contradiction that [IP] > Then there would have been added more than n solutions to Q, such that for all æ * y E Q it holds that either f2(x) > 2f2(y) (y) fy(y) > 2f2(2). Since all solutions correspond directly to pairwise distances in d2 of our point set P. this a contradiction to Lemma 39 and therefore the corollary follows.
B.3 Combination of k-center//-diametle with k-median/k-meann
We consider the combination of k-center with k-median or k-means with respect to two distinct metrics dj and d2. It is easy 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 PP| < a(n 1) Alamdari and Shmoys [5] show that we can compute the approximate Pareto set Fa for a (4,8) with respect to f1 rad and f2 med and the special case where di = d2 They modify the LP-based approach by Charikar et al. [2 for k-median to compute solution which is also good approximation to the radius.
In similar way we show that the approach for k-median by Jain and Vazirani [1] can be modified compute the approximate Pareto set F., for a (9, 6 + e) in the more general case di # d2.
Theorem 41. Given finite set P, two metrics dı, d2 P, k E N. If for R > 0 there exists solution (C, a) for P with (C,(C,Co a, di) < R we can compute a solution (C', o²) in polynomial time such that rC", o', d2) < 9 R and med(C", a² d2) < (6 +6+6 e) med(C, a, d2).
Since the algorithm in [41] also produces a (54 + jaaprooximation for k-means we can also adapt it compute the approximate Pareto P., for (9, 54 + <) for the case S1 = rad and f2 mean.
Theorem 42. Given finite set P, two metrics d1, d2 P, k E N. If for R 0 there exists solution (C, o)) for P with rad a, d1) < R we can compute a solution (C', o²) in polynomial time such that rCd(C", o', dd1) < 9 R and mean(C", o', d2)) I (54 + c) mean(C, o, dz).
We assume that the algorithm by Alamdari and Shmoys 5 for k-center and k-median can also be adapted the combination of k-center and k-means with adjusted approximation factor.
For the case fi = rad and f2 = med we can compute the approximate Pareto set P., for a = (9, 6+)) by checking all n(n-1) possible values for the radius R. Suppose there exists k-center solution for P with radius -/2 R and let (CR, be such a solution that minimizes the k-median cost. Theorem 41 implies that we can compute solution (Cn,, ox2) with fi fi (in < 9 R and med Ch Z2. S (6 e) med(C n, d2) polynomial time. Let P., the set containing all these solutions, then P. is a-approximate Pareto set. Following the same approach we can
30

---

compute the approximate Pareto set Pa for a (9,54 + c) in the case fi = rad and f2 mean. This yields the following corollary.
Corollary 43. Given a finite set P, two metrics d1, d2 on P and k e N. We can compute the approximate Pareto Fa for
α (9,6+ 1.6++0 E) with respect to the objectives fi raa and f2 med
a (9,54+ with respect to the objectives f1 = rad and /2 mean
in polynomial time.
To combine k-diameter with k-median/k-means we observe that any solution (C, with diam(C, a, d1) R satisfies rad(C, a, d1) v R. By Theorem 41 we can compute a solution (C",a') o') with diam(C", o', di) s 2rad(C"o' d1) < 18R and med(C"o d2) S (6+e)mm (Ge+))me((C d2) in polynomial time. similar statement holds for the combination of k-diameter and k-means by
Theorem 42
Corollary 44. Given a finite set P, two metrics dı, d2 on P and le N. We can compute the approximate Pareto set P for
(18, 6 + c) with respect to the objectives fi diam and f2 med
a (18, 54 <) with respect to the objectives fi diam and f2 mean
polynomial time.
To prove Theorem 41 we repeat the (6 + +) approoximaaoo algorithm for m-median proposed by Jain and Vazirani 41 and explain the relevant changes to obtain a solution which also approximates the we first develop an algorithm for the facility location problem.
radius. Following
In the facility location problem we deal with set F of possible facilities and set D of clients. Furthermore we are given metric d on F D and facility opening costs f(i) for every F. The task is to compute set C C F which minimizes the sum of opening costs and distances between a client and its closest facility Evec f(i) + EjED minger dii..j). Later, when we use algorithm for facility location to solve the k-median problem on the set P. we set F P.
We consider the combination of facility location with the k-center objective. Suppose we are given two metrics d1, d2 F and want minimize the facility location cost (with respect d2) as well as the maximum distance between client and its facility (with respect to dj). Now a client may not be assigned its nearest facility with respect dg, since this may result in a large radius with respect to d1. Thus we say that a solution consists of set C C F and an assignment a: D - C of clients facilities. We seek to minimize the objectives oC, fac(C, a, d2) = Eieo f(i) + EjED d2(}. (j))..
maxjeD di (j, (j))(j)) and
Theorem 45. Given set of facilities F with opening costs f(i) 2 0 for E F, clients D, two metrics dı, d2 on FUD and a number R thee exists a solution (S, 7) with rad T, d1) R. then we can compute a solution (C, .) in polynomial time such that rad (C, d1) I 3 R and 3 E.ec fi) + Ejen d2(j, a(])) < fac(S, d,d)).
For some radius R > O we want to compute an optimal facility location solution with respect to da under the side constraint that the radius of every emerging cluster is at most R with respect to di- We consider the standard formulation of the facility location problem as integer program with the additional constraint that a client can only assigned to facility if it is at a distance at most Let M {(i,j) E F.j D, di.j)) < R} be the set of all such combinations. We consider the
31

---

following integer program.
minimize
Σ
1(0y +
Σ dz(i,
iEF
(I.))M
subject to
Σ Tij 21 1 (K
Vj E D
Fij S Yi
V(IJ) E M v(I.) E M ViEF
Fij {0,
E (0,1)
Given an optimal solution (æ. y) of this program we open a facility i F iff = and assign client j to iff Tiy 1. Let (C, 0) the respective solution for facility location. easy to see that we have rad(C, a, d1) s R since we only allow client to be assigned to facility within distance of R with respect d1.
To obtain the linear program we relax the last constraints to Taj 2 0 and y/ 2 0. Its dual then given by
maximize
Σ
dj
JED
subject to
aj
Bij S d2(i,j)
V(i,j) M ViEF
Σ Bij S Si
00
VjEl v(i,j) M
Bi 20
We construct solution for the dual LP by starting with a, 0 for all D and growing them simultancously at the same rate until some stopping condition is met. Later on the variable ay 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 unconnected. While time proceeds increase all variables of unconnected clients uniformly such that if client j is unconnected at time t we have 0j = at this time.
We have to maintain the feasibility of the solution. There are two types of events at time / which can violate the feasibility.
The first type of event happens when there unconnected client j and (i.j) e M such that ay de)). In this case we declare (i,j) to be tight. If facility is open we declare j to be connected Otherwise from time on we have to maintain the constraint 0, - Big S dz(i, by starting to increase B.j at the same rate as aj.
The second type of event happens when there is facility i such that E(seeM Big f().. In this
case we declare facility to be open. Furthermore unconnected clients j with (i. tight are declared to be connected to i.
We stop the process when all clients are connected. Let C' be the of open facilities the end of this process. For a client let d'(j) if is declared connected to facility i. Then (C", o') is feasible solution to the facility location problem with rC' o', dd) < R. We would like to bound the facility location cost fac(C", a', d2) in terms of Ejec ay. However it is not possible to upper bound the facility opening costs for facilities in C", since for client there may be multiple facilities
32

---

i E C" for which Biy > O. Thus aj pays for opening multiple facilities from C". Therefore following the work of [4]] we will close some of the facilities 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 graph G on C" as follows. We connect
two facilities i, i' E C" by an edge if there exists a client j with Baj > 0 and 3rz > 0. Then let C" C C" be a maximal independent set in G. For a client j we assign facility from C" follows. If there is a facility i E C" with 3.j > 0 we set a(()) = i and call j directly connected. Since C" is an independent set, this facility even unique. If there is no such facility in C", we consider the facility i which j is assigned to in (C", ,'), i.e., = o' (j). If i E C" we set o"(i) i and call, j directly connected. Otherwise we know by maximality of C" that there exists a facility i' E C" which is connected to by an edge. In this case we set (i) = i' and call j indirectly connected.
Lemma 46. For the solution (C", ,"") computed by the algorithm we obtain 3 EiEo" f(i) SSEDd2li (a(j,o"())) (i) E3Ejen Oj and rad(C", ,"",,) di) < 3R.
Proof. Let D1 C D be the set of directly connected clients and D2 C D be the set of indirectly connected clients.
For facility& i E C we know that f(i) = EUJJeM B.g = EiED, ()o"()) Sty. Where the first equality holds, because was declared open by the algorithm and the second equality holds, because all clients j E D with Bey > have to be assigned to by o" and are directly connected.
j E D and i = o"()). If is directly connected we know that (t. E M and = .eg + d2 (i.
If is indirectly connected we claim that (i S 30r.. Let 1 o' d')),, since j is indirectly connected, we know that and i' are connected by an edge in G. Thus there must be a client j' E D with Big and Bey > O. We know that ag = SBy + d2 (i) and ag = Buy + d2('', J"), so therefore dz I ag and d2 < ag' Let t be the time when facility is declared open by the algorithm and the time when 7 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 {'} and therefore a' S min 8'.. On the other hand we know that t' aj since o'()) y'. In total we obtain by triangle inequality, that di S dz(i,,") + dz(l' 11) de(l' S 2ay + aj I 3a.. Altogether this implies
3 3 f(i) +
Σ
do(i, o -()) =3 Σ
Σ
Big +
Σ aj - -Bor(133 + Σ 3aj
VEC"
JED
iEC" jEDi: i=o"())
jED,
JEDz
<3 Σ
Pa" +
Σ
aj aa- Bo"( + E3ay
3ay
jED
JED1
jEDa
< 3
Σ
aj-
jED
This yields the first part of the lemma.
For the second part let j be client and = d")). We have prove that di (i, S 3R. If is directly connected we have (i, E M which implies di ji, < R. If is is indirectly connected let o' (j) Notice that this implies (7),)) E M. Since is indirectly connected, we know that and i' are connected by an edge in G. Thus there must be a client j' E D with Bag. > 0 and Bry > 0 and therefore (i.)"), (i', (') E M. We obtain di (i. S di. + di' + (i. S 3R.
We are now able to prove the theorem.
Theorem 45. Given set of facilities F with opening costs f(i) 2 0 for i E F, clients D, two metrics di, d2 on FUD and a number R > 0. there exists a solution (S,T) with rad T, d,) S R. then we can compute a solution (C,o) in polynomial time such that rad(C, o,,, 1 3 R and 3 Eiec f(i) + Ejen d2(), < 3 fac(S, T,))).)
Proof. Since (S,7) is an integral solution to the LP with radius Rt, we know that the above algorithm
computes a solution a for the dual LP with EjeD a, S fac(S, r, 7, Let (C". oa)) be the solution for facility location computed by the algorithm. We can apply Lemma 46 to see that Cad o" od.d) dd) S
3 R. and 3 Eiecr f(i) + ESeD dz(j, o"))"(()))) I 3fac(S,T,,d))
33

---

Given some radius R > O and set of points P. We originally wanted to compute an optimal k-median solution of P with respect d2 under the side constraint that the radius of every emerging cluster is at most R with respect to d1. We consider the following formulation of the k-median problem as a linear program with the additional constraint that point can only be assigned to center if it is at distance at most R. Let M = {(i. f) i, E P, di (i I RJ be again the set of all such combinations. We consider the following linear program.
minimize
Σ
(iJ)EM
subject to
Σ Tij 2 (1.))EM
VjEP
Vij S
v(ij) E
Σ 1/4 S
iEP
Ty 20
v(Ij) E
V/ 2 0
ViEP
Its dual is then given by
maximize
Eaj- zk
JEP
subject
0j Bij S d2(i,))
v(i,) E M
Σ Bij 2
ViEP
(K
0j 0
VjEP v(i,j) E M
Bg 2
x 2
Let (x*,y") and (a",8", 2*) 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 [1] we introduce 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 facility equals f. We can use Theorem 45 to compute a facility location solution (C, a)) for this instance. Let (a, 3) be the respective solution for the dual program computed by the algorithm, then Djep d2 d2(5,a())) a()) < 3(EjP aj- -(c"). Thus if |C| we that (a,, 3, is feasible solution for the dual program with cost Σjep 0j - [[C and therefore med(C, o, d1) d I 3(E 3 Ejer di
f(C1) s 3(E 05 =*k)
However cannot rely the existence of facility cost f such that the algorithm for facility location outputs a solution with exactly l centers. Instead for c >> O we can find via binary search cost fi such that the respective solution (C1,a1) for facility location consists of kı centers and the cost f2 such that the respective solution (2),02) for facility location consists of k2 > k centers and If2 fil éddii where dmin min jitj d2(i,)). We slightly modify the randomized Sn
rounding algorithm by [41] for k-median to select & centers C' C C UC2 such that in the end we obtain solution with [[med(C, o, d2)) S 6 GjEE d2(i, f)xty and rad(C, d,di) < 9R. We only explain the randomized rounding and do not go into detail about the binary search for fi and and the derandomization of selecting C C C1 U C2. since this can be done analogously to [41.
The randomized rounding works as follows: Let a
Furthermore for E C1 consider the set k2-ki
k
T. (i' C2 o (i) noz (f') + 0} C C2. For every i C₁ let e(i) argmin/er;d di (i', i) and
34

---

set Cy = {c(i) E Cit UT where T' is an arbitrary set of centers from C2 \ C2 such that in the ky chosen uniformly random from C2 C₁2 With probability a we set C = C1 US. For point j E P if (2( E S we set a o2(i) and otherwise a(j) = =1 (j). With probability - a we set C C%2 U.S For a point j P of E C, we set a ا2 and otherwise o(j) = ()))
end [cy] kj. Let S be a set of cardinality
The difference to the rounding procedure in [4]] lies in the choice of C₁ To ensure that the radius with respect to dj can be bounded, we are not allowed to simply set C22 as the set of points in C2 closest to C1. With a simple modification for C22 we can ensure that both the k-median cost and the radius can be bounded.
Lemma 47. We have E(med d2)) S (6 + 2c) E(sEEM (1,)) and rad(C, a, d1) 9R.
Proof. For point j P we distinguish two cases. If 02(1) E C22 then E(d2(j. = a d2(i.0100) + (1 a) d2(j. If oz E C2²C2 then with probability have (2) C and d2(1, (j)) = d2(i, with probability a² we have 02 $ C, E C and d2(j.o(i)) = (i)) With the remaining probability a(1 - a) we have
k-bL h--h = =1- a we
dz(j,o(i)) = dz(j: c(r) S da(j, (a(()))))))
- 2dz(j, 01 (J)) d2).
Where the second inequality holds because o2( E To, and c(ai (j))) is the closest center to o1 (j) among all centers in ()) In total we obtain
((dz(j,((i)) (1 of
+ - a) (1)) d2
Therefore
E
d2(i. s 2(a Σ
d2) + (1- a) Σ o2)))
JEP
JEP
jEP
It is left prove
a Σ
Σ
21,d2(1.1).
jEP
jEP
(L.)MM
Let (g(0) be the solution for the dual facility location LP associated with the solution (C,, o,)
for 1,2. Observe that by Lemma 46 we have
Σ dd((io,)1i) jEP
S 3(
Σ (1)
f(k)).
jEP
Moreover if we use fi f2 S ddmin we obtain
(1 - Σ deli - 3
Σ fik2) + 3(f1 f2)k2 - è Σ dz(i,
jEP
JEP
jEP
3(
(2)
-1k2) + +2dminn -2dmii
JEP
3(
0 -f1k)).
(2)
JEP
Finally we get
Σ dd(( + (1- Σ de(j.o2()) (3+ (3+c)) Σ aaj
+ (1 -0)a (2)
fik)
jEP
JEP
JCP
$ c3++)
Σ ++dd2(1.)))
(1.)eM
35

---

Where the last inequality follows from the fact that (aal) + +11-(1111111 (1-a)a(),aa) a.8 + (1 (110)++1-0000)))0 (1-a) fi) is feasible solution to the dual the k-median LP.
To bound the radius of (C, a) with respect to d1 we observe that for every point j E P we have (j) E
{ar (j), (2(;), c(ar (i)) In the case a(j) oz(s)
di (i, oi, S 3R
and in the last case we use that there exists point j' with oı = 01 and =2 do,
and thus by triangle inequality c(aa (i))) - +
2ra,(Ci, a1 d1) + rad(C2, T2 d1) S 9R.
Theorem 41 follows immediately from the previous lemma.
The algorithm in [41 also extends to squared distances and yields a (54 + -)aprooximtaionn for k-means. Notice that the additional factor of 2 in the Euclidean space mentioned in [4] can be omitted since we restrict the set of possible centers to P from the beginning. Theorem 42 summarizes the results for k-means.
B.4
Combinations of k-mediaa and k-means
We first prove that the size of the Pareto can be exponential for the combination k-median and k-means even if d d2. For this purpose we present small construction that consists of several points which should be covered by one center in the final solution. Both the optimal center and the value of the 1-median solution differ from the optimal center and the value of the 1-means solution in this construction.
Let M C. Rn be such construction and d1 (a, y) = (z, y) = - - yl. In the following we denote by C1. C2 the optimal 1-median and the optimal 1-means center, respectively. Furthermore let a; = Σ p Ip c,l and 3; = Epen Ip a for i {1, 2] and assume that < a2 and 31 > 32. An example of such construction is given in Example
We now construct instance P with exponentially large Pareto set by combining several scaled versions M. Let M, = {2> 2 + X A x E M) and c² = 2a o + X for i E {1, 2} and 2 12 where 8 denotes the maximum diameter of M. Define P to be an instance consisting of Mo. M1, M2, M3. MRr...,MM-I. Thus P consists of k substructures, each of which should be cluster of the optimal k-clustering for both cost functions.
Theorem 48. For every k there exists a point set C such that for di d2 ||:11a and fi med, mean we have [P| > 2*
In order to prove this theorem, we look at the 2* clusterings that are constructed by choosing either of or c³ as center of each of the & different substructures M4. More formally, define for 1 C [k] the center set C₁ which contains of iff i I and e₁ otherwise. For all M, we set or(p) cj if oi E CG and (p) = o, if ef E C₁.
The following lemma shows that every such center set induces a Pareto-optimal clustering, which directly proves the theorem.
Lemma 49. (C1,01) is Pareto-optimal for all I C [k].
Proof. We prove the lemma by contradiction. Assume there is an I' such that (Cr, σy) dominates (I), We consider two cases.
2
Figure 6: Example for the construction M. The numbers below indicate the numbers of points on the location.
36

---

Case 1: 21 > EiEry 2
In this case we know
mean(C1, 11-1122) =
Σ
22
Σ
2
VEI
i&!
Σ
2 + Σ
2 22i-2B1 Σ
20i-332 32 + Σ
22i-2
1ET(U
iEINI'
VEP'
iNTUN'
2 31 + Σ
2
22-228
B1 + Σ
22i-2
32
Σ
2
iETNI'
i$IUP
Σ EE
2
B1 + Σ 2
i41
mean Cr, 01', 11-112)
where the inequality holds because Eiery 2 > Eien, 2 and the 31 > 82. This contradicts the assumption.
Case 2: Eiemy med(Cri,or, 111111,,, which also contradicts the assumption.
2 2 < 2
2'-1. Here we analogously get med I1-112)
<
By the construction of P we know that (Cr, ar) cannot be dominated by any other solution (C, o). easy to observe that if M, contains a center that it is always better to assign all other points within this center independently whether we consider the k-median or h-mmaans objective. Thus for any Pareto-optimal solution (C, o)) that dominates a solution (C₁, oy) there exists a non-empty set U of indices such that for all E U there is center chosen within M,. 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, contains only single center, choose an arbitrary center in M; for any i E U and for all j E (0. k - }} reassign all points in Mj to the respective center. For each index d E U the f-meddia assignment cost of any point in M, gets reduced from at least A - 8. 2 to at most -2 At the same time the assignment cost of any point contained in cluster where point gets removed increases by at most 5- 2 while the cost of the remaining nodes stays the same. Thus the k-median cost decreases by least [M
352=-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 the solution (Cr, is Pareto-optimal and the lemma follows.
In the following we see one possible example for the construction M. Example 50. Consider 5 points
line, where the distance between the first three points and the second point is I and the distance between the second and the third point is 2 (see Figurelo). Then the optimal median center is one of the leftmost points, while the optimal mean center is the single point in the middle. Therefore 01 =4, 4, 0r2 = 5, B1 = 10 and 32 = 7, fulfiliing the prerequisites on M.
Even though the Pareto set of this combination may have exponential size, Papadimitrou and Yan- nakakis [49] showed that there always exists an (1 + 6, + ---appooxim Pareto set, whose size polynomial in the input size and They furthermore showed that there is polynomial algorithm to construct such an (1 + e, 1 + -)-aprooxem Pareto set if and only if one is able to solve the following problem in polynomial time: Given the instance and 61, b2 R, either find a solution s with (())) < by for i {1, 2 or report that there is no solution s with (1 + f))(()) < by for i E [1,2}. Unfortunately, for f1, f2 E {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 an = az, we write CP, instead of CP,,. for convenience.
Theorem 51. Given a finite set P, metrics d1, d2 on P and two objectives f2 E {med, mean). Lei e > Then we can compute an (8 + -)appreeximate convex Pareto sei CP in time that is polynomial in the inpul size and 2, where ö = 2.67059 if fi med and f2 med, and 8 = 9 + if fi = med and f2 = mean or J1 = mean and f2 = mean. The size of this set [CPotel is also polynomial in 1 and PP.
37

---

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 fi, f2 be minimization objectives, and (wi, w22) E TR2 weight vector. Then we define the related Comb-proe Comb-problem to be the problem that seeks to minimize the weighted combination of both objectives w f w1 fi + W2- -2- f2.
We denote by Combs(w) routine that returns a 8-approximate solution to the Comb-problem with weight vector w. We will show that polynomial time Combs(w) routine is enough to compute (6 (1 + - -pppapoxiimmtte convex Pareto set to the bi-objective original problem II for all e > 0. To achieve this, will describe a scheme which returns such set where the number of calls to the Comby routine is polynomial in - 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- comb-problem is sufficient 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 E R is called approximately balanced if both its coordinates are within factor 2 of each other. We will first construct a set to (6 (1 + cover all approximately balanced solution points Stat, 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 e > 0 there is a set of size O(2) that (1 + c)-covers all approximately balanced solution points. We want to compute d-approximation to such a set using only 0(2) many calls to Comb3- Therefore we are looking for set of weight vectors Wbal with (Dall E ( whose corresponding solution set Qral = (Combs(w) w E ]ba) contains a (8 (1 + e)) appproxiieeee convex Pareto set of Shal-
We will now define the set Whi in way, that only dependent on c, but not on the given problem instance. For that purpose, we set M = 2 Let What {11, _ ), ( 1) | [M]] It is easy to
see that |Waal E (2)) Therefore we can compute Qoal with O many calls Combs. Let Qia be the convex Pareto set of Qbal-
The following lemma shows that the set Qia is in fact a (5 (1 apprrxximttee convex Pareto set for all approximately balanced solution points.
Lemma 52. For every approximately balanced solution point s Spat. there is a convex combination of points in Diat that (8- (1 + c)) -covers it.
Proof. We first prove the following claim: For any weight vector w E R2 there is a solution q" Qin such that w q < 8(1 c)w+s
Let w = (W1, W22 be an arbitrary weight vector. By symmetry and by scaling of the weights we can without loss of generality assume that We S W1 1. Let w² be (W1, wy). where wž arises from 1 w2 by rounding up to the next higher multiple of X7- It follows that w² E What and therefore was considered by our scheme. Let q² be the solution point given by Combs(w").
By the definitions of wn and of Comb, the following holds:
unq"
S w w²q"
S 8 w²s
8. (wi 81 + +w 82)
W22 + 1
S 8 (wi 81 +
82)
M
8. fwss +
82)
M
2
< 8. (ws
M $1)
(2)
2
< 8. (ws
M w8)
< 8. (1 + c)ws,
38

---

where inequality 2 follows from the fact that is approximately balanced and inequality (3) follows from the fact that w1 1 and therefore st contributes directly ws. This proves the claim.
Let q = (91,92) (2) be the point that lies on the border of the convex hull of Q and fulfills 2l
q2
(therefore intersects the line between & and the origin).
Let q',"' be the solutions in 2ia such that of S qi S qi and there is no p E Oial with of S S qf Let (1,w") w'), (1, w²" be the weights that generated 9¹ and q²,, respectively.
Then we know that for all weights between w' and w" either q' or q" are approximately optimal (since w- p is linear in p and w for all p). Therefore there is a w = (1, w²) with w" I ww" I w such that of w q" and both points are approximately optimal for this weight. Since q convex combination of o' and q" we know that wo w.w S 6(1 + +e)w- 8. Together with 인1 92
it follows that s approximately dominated by q which is a convex combination of q', qq" Qial-
Since normally not all solution points are approximately balanced, 2id might not cover all solution points. Diakonikolas shows that this can be taken care of by looking multiple different scalings of the objective functions such that for each point of the solution space there is one scaling such that approximately balanced in the scaled version. He furthermore shows that a polynomial number of scalings is sufficient.
This proves that for all e 0 one construct ((1 + e) -)-coneex Pareto set whose size is polynomial in if there is polynomial Combs-routine. The runtime of this construction is also polynomial in 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 d1, d2 be two metrics. Then the following hold:
1. There is a
for f1 = med and fz = med.
2. For all é' > 0 there is Combiu+-routine for f1 = med and f2 mean.
3. For all é > 0 there is Combo+..-routiin for fi mean and fz mean.
Proof.
1. Since for any weight vector RR3 the function d' w1 d1 + w2 d2 is again metric, the Comb-probled can be solved by any approximation algorithm for the k-median problem under general metries. The currently best known algorithm is from Cohen-Addad et al. [6 and achieves an approximation factor of 2.67059.
2. The algorithm for k-means in general metrics by Ahmadian et al. 4 extends to all sum- based cost functions of the form EpEp c(p, (p)) whose distance function c(i, j) fulfills the inequality j( I 3(c(i, k) + c(k,l) + c(l,j)). The combined objective for the k- means and k-mmedian cost-functions for arbitrary weight vector w E R2 is given by w1 med(C, a, d;) + u2 mean(C, d2) wh Epep di (p, (p)) + u2 Epep (p)))(()) Epep wi di (p, a(p)) + w2 op)) Thus all we have to do order to apply the algorithm to our objective is to show that c(i, wi di (i,j) + w2 di fulfills the
necessary property, which is done the following:
c(i,j) = wid1 (1,5) + (idB(i.))
< +d( (66()
=
+((.5) < (i, (k. w (1,s) +2d
3(((i, k)) + I(k, cllj)))
Therefore we also achieve the factor e for the combined cost function using the algorithm in
39

---

3. This works analogously to 2., by setting c(i. = w1 dd((,)) + w2 dB(i.)) instead.
The theorem now follows directly from Lemma 53 and the factor achieved by our scheme.
C More Details on Experimental Results
C.1 Improving k-means++ by combination with separation
We test the approach to combine k-means with separation presented in Chapter A..3 on data sets with ground truth inputs 2 26 6 3 34 32 33). We hope 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
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 i for the approximate Pareto set 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 data set of size there are only O(n²) possible values for the separation. We compute these values time (nndd) and sort them in increasing order time (nn lng( 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 merge all points whose distance is at most A. This can be done efficiently via a Union Find data structure. Since the resulting clustering may have more than & clusters, we have to reduce the number of clusters to k. For data sets in IRd and the k-means objective, one 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 (running time O(nkd)) and to produce solutions of high quality for
the k-means problem in practice. Then the respective clustering on the original data set has separation least A and most & clusters. One can show that this algorithm computes an a-approximate Pareto with a = (1. (log k)).
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 F3-scores for B == 0,5, 1, We briefly recall their definition below. For every measure we pick the clustering in the approximate Pareto set that has highest value with respect 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 h = 1,..., 7 and we compute the highest values achieved by these clusterings. In the second variant we fix & 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
Data Sets.
We tested the algorithms on the following data sets.
Iris 26 150 points, = 4, k =
Dry Bean 2 13611 points, d = 16, k- = 7
Rice 1: 3810 points, d 7, k
Wine 3:
178 points, d = 13, k = 3
Optdigits 6 5620 points, d = 64, 1 = 10
2d-4c-no3
34 (Figure 7a): 1123 points, d = 2, k
2d-10c-no3
32
(Figure
kb 3359 points, d= -, = 10
2d-10c-no4
33
(Figure
7c 3291 points, d = k 10
40

---

(a) 2d-4c-no3
(b) 2d-10c-no3
(c) 2d-10c-no4
Figure 7: Visualization of the ground truth for the three synthetic data sets.
Results. The results show that for all data sets except rice and all measures the best solution in the approximate Pareto set has 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 data set 2d-10c-no4 in Figure & that Single Linkage reconstructs all of the larger clusters when performed for appropriate separation value and performs better than k-means++ with k: = 10 (Figure (a). However the number of clusters large (k = 85) since there are some outliers which in separate clusters. If perform Single Linkage for lc 10 clusters containing most of the points and clusters with at most 2 points each. The best solution in the approximate Pareto set (Figure [d) mostly coincides with the solution found by Single Linkage in Figure [c 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 and Figure 10.
that the result is two large
Based on our experiments the combination of k-means++ and Single Linkage can be useful
reduce the number of clusters found by Single Linkage or
improve the quality of the k-means++ solution.
On all data sets that not synthetic, the best result in the approximate Pareto set has small separation, as we see in Figure [22 Therefore we assume that it is sufficient to execute the algorithm for small separation values instead of computing the whole approximate Pareto set improve the quality of the solution. Notice that on the data sets rice, wine, and optdigits the best solutions on the approximate Pareto for some measures are the ones with smallest separation. However it does necessarily coincide with the solution found by k-means++ and in fact performs better with respect NMI, RI, and Fa-scoress. For visualization of NMI on the approximate Pareto set we refer to Figure 13 In Figure [4] one can see the variance of the measures for k-means++ and the approximate Pareto
Resources and running time. The experiments were performed on a machine with a 2.7GHz AMD Ryzen PRO 6850U processor and 32GB RAM. The source codes are C++ and available at https://githuu com/ algo- www.aahhggaaaaaoo the k-meanst+ 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 1 11...0 with optimization flag -02. Since the experiments are performed for 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 measures took at most 15 minutes per data set.
in folder &Means_St. The first draft of
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 value of 1 is achieved when the computed clustering matches the ground truth. For detailed survey on such measures we refer to (54) Let (C,a) the computed clustering and (C*, a²) be the ground truth. For E C,j C let
P. = (p P ( i,) = j} be the set of points assigned center by the computed clustering and j by the ground truth.
41

---

-10
-10
(a) Clustering by k-means++ for 10.
(b) Clustering by Single Linkage for k = 10.
5-
-5-
-5-
-35
-10
10
15
-15
-10
(c) Clustering by Single Linkage for separation A
(d) Clustering on the approximate Pareto curve for
0.67 and l: 85.
k
10.
Figure 8: Clusterings computed on data set 2d- 10c-no4.
P.j = E dp()) = j} be the set of points assigned to j by the ground truth,
P.. (p E (p)) i} be the set of points assigned í by the computed clustering,
Pij = Pul Paj [P.,] and Pi= |P.-
Rand Index: The Rand Index is defined by Rand 51
Let the set of true positives be TP
{[i,j} i E P,i # (i) o(j) and o (i) o² (i), i.e., it contains pairs of points which are contained in the same cluster both in (C, and (C* ("*, Furthermore let the set of true negatives be TN {{i.]] i,j E P.i + j. + a and (i) + o (i)) i.e., it contains pairs of points which are contained in different clusters both in (C, and (C*, (o)). The Rand Index defined as
RI(C, 2(TTP + (TN)
n(n - 1)
F3-score:
The F-score was introduced in the context of clustering by Larsen and Aone 44 For centers i C and j C",, define the precision Prec(i.j) [P,. and the recall as [P..
Rec(i,,) IP..
We combine their definition with the general definition of an Fa-score in binary classification by van Rijshergen (53] and obtain the F3-score cluster and j as
Prec(i, j) Rec(i,
Fa( = (1 + 3²)
3a Prec(i.j) + Rec(i.
The F--score of (C,o) then defined as
Fo(C,
1
Σ
|P max Fo(i.j).
n jEC
iEC
42

---

75
75
30
-10.0
-10.
(a) Clustering by k-means++ for 4.
(b) Clustering by Single Linkage &
75
50
7.5
75
-10.0
-10.0
(c) Clustering by Single Linkage for separation 1.37088 and & 11.
(d) Clustering on the approximate Pareto curve for
k ==6 4.
Figure 9: Clusterings computed on data set 2d-4c-no3.
Normalized Mutual Information: We also consider the Normalized Mutual Information as defined
by Fred and Jain (7).
2 NMI(C,o) H(C,o) H(C", jEC
Σ
Σ Pig log Pdj PajPie
where H(C, = = Eiec Pia log(p:.) and H(C",a") = -E Paj log(paz) are the entropies of the clusterings (C, a) and (C*,a*)
43

---

15
10
10
5-
-10
-10
-15
-15
(a) Clustering by k-means++ for 10.
(b) Clustering by Single Linkage for k = 10.
15
15
10
10
-10
-10
-15
-10
10
-15
(c) Clustering by Single Linkage for separation A 0.36 and lo = 243.
(d) Clustering on the approximate Pareto curve for
k == 10.
Figure 10: Clusterings computed on data set 2d- 10c-no3.
44

---

Measure
k-Means++
kMcans++ with k=3
Single Linkage
Single Linkage with k=3
Pareto front with k=3
RI
0.8734
0186633
0.8836
0.3289
0.9379
0.8829
0.8780
0.8838
0.5000
0.9481
F2
0.8865
0.8807
0.8412
0.7143
0.9476
FO.5
0.8964
018827
0.93499
0.3846
0.9512
NMI
0.7452
0.7405
0.7070
0.0000
0.8578
dry-hean Measure
k-Means++
kMeans++ with k=7
Single Linkage
Single Linkage with k=7
Pareto front with k=
RI
0.8279
0.8026
0.8274
0,2470
0,8069
0.6016
0.5944
0.3975
0.3348
0.5968
0.7091
0.6339
0.5369
0.6453
FO.5
0.6130
0.5713
0.3647
0.2503
0.5772
NMI
0.5277
0,5164
0l3753
0.1626
0.5231
Measure
k-Means++
kMeans++ with k=2
Single Linkage
Single Linkage with k=2
Pareto front with k=2
RI
0.7892
0.7892
0.6325
0,5104
0.7888
0.8794
0.8794
0.6729
0.6728
0.8792
0.8796
0.8796
0.8353
0.8351
0.8794
FO.5
0.8802
0,8802
0.7123
0.5647
0,8800
NMI
0.4693
0.,6933
0.2334
0.0007
0.4728
Measure
k-Means++
kMeans++ with k=3
Single Linkage
Single Linkage with k=3
Pareto front with k=3
RI
0.7148
0.7105
0.6862
0.3628
0.7199
0.7145
0.6919
0.6804
0.5029
0.7241
F2
0.8123
0.6982
(1.6676
0.7036
0.7771
FO.5
0.7224
0.7034
0.6452
0.3921
0.7440
NMI
0,4278
0.4265
0.41005
0.0615
0.4400
opidigits Measure
k-Means++
KMeans++ with k=10
Single Linkage
Single Linkage with k=10
Pareto front with k=10
RI
0.9528
0.9320
0..9244
0.0998
0.9390
Fl
0,8322
0.7854
0.1818
0.1818
0.8137
F2 0,8216
0.7992
0L3572
0.3572
0.8246
FO.5
0.8748
0.7864
0.2355
0.1220
0.8149
NMI
0.7846
0.7459
0,4627
0.0000
0.7627
2d-4c-no3
Measure
k-Means++
kMeansi+ with k=4
Single Linkage (1.9943
Single Linkage with k=4
Pareto front with k=4
RI
0.9645
0..6455
0.7243
0.9941
0.9726
0.9726
0.9960
0.7538
0.9955
0.9725
0.9725
0.9952
0.8759
0.9955
FO.5
0.9732
0.9732
(1.9968
0.6724
0.9956
NMI
0,9052
0.9052
0,9792
0.7260
0.9779
2d-10c-no3
Measure
k-Means++
kMeuns++ with k=10
Single Linkage
Single Linkage with k=10
Pareto front with k=10
RI
0.9795
0.9655
0.9850
0.7943
0.9894
0.9209
0.8803
0.9116
0.5431
0.9684
0.9294
0.8895
0,7302
0,9698
FO.5
0.9409
0.8867
0.9382
0.4374
0.9686
NMI
0.9260
0.9065
0..1188
0.6763
0.9491
2d- 1--440n
Measure
k-Means++
kMeuns++ with k=10
Single Linkage
Single Linkage with k=10
Pareto front with k=10
RI
0,9724
0.9597
0,9906
0.6056
0.9817
Fl 0.8874
0.8608
0.9715
0.3735
0.9410
0.8707
0.5825
0,9495
FO.5 0.9157
0,8691
0.9871
0.2767
0.9447
NMI 0,8933
0.8715
0,9409
0.4631
0.9267
Figure 11: Highest values achieved by k-means++ for arbitrary kt k-means++ with fixed k, Single Linkage for arbitrary k, Single Linkage with fixed k and approximate Pareto set with fixed k. Whenever & is fix, we fix the cluster number in the ground truth.
45

---

x1612
7.0
8.0
6.0
7.0
6.0
K-means caSE
5.0
5.0
3.0
2.0
R1.F1.2.FO.55 point
1.0
FLF.1,2,0..5.0M point
point
5000
4000
Separation
Separation
(a) iris, = 3
(b) dry bean, k = 7
X10.0
x107
2.2
RLF1.00. 105:: poin. 1 point
2.0
NMI: point
3-heans COST
1.5
1.2
1.0
R.FL.F2.F0.5:
0.4
NMI: point
0.2
600
500
400
300
200
100
60
50
40
30
20
10
Separation
Separation
(c) rice, & =
(d) wine, A = 3
x30
x10
4.5
5.0
I-means cost
4.0
3.5
3.0
3.0
2.0
RUNMI: point
point
1.0
point
70
40
0.25
(c) optdigits, 10
(f) 10c-no3,
x10
2.0
R1,F1.F2.FO55 5... point 19
1.2
FLFFL.2.F0.55.00 point
1.8
1.2
0.4
0.8
0.2
2.5
1.0
0.5
0.0
1.2
1.0
0.8
0.4
0.2
Separation
Separation
(g) 2d-4c-no3, le =
(h) 2d-12410 1d--04,,,4, = 10
Figure 12: Approximate Pareto curves. The highlighted points show the solutions on the curve with highest NMI, RI, Fcoores.. The points on the curve are numbered from right to left.
46

---

Noraaized alized Mutual Information
1.0
1.0
NMI:0.522367
0.8-
0.8-
0.6
Mutual
0.4
0.4
0.2
0.2
0.0
7
5000
4000
3000
2000
1000
Separation
Separation
(a) iris, = 3
dry bean, k
Normelized Mutual Information
1.0-
NMI=0.473471
Information
044961
0.8
0.6-
0.6-
0.4
0.0
0.0
500
500
400
300
200
100
60
50
40
30
Separation
Separation
(c) rice, & 2
(d) wine, A
Vormalized Mutual Information
1.0-
NMI=0.765081
1.0
NM|=0.952255
0.8
0.6
Normalized Mutual
0.4
0.4
0.2
0.0
70
0.25
Separation
Separation
(e) optdigits, & = 10
(I) 2d- 10c-no3, & 10
Normalized Mutual Information
1.0
Information
NMI-0.9377
0.8
0.8
0.6
0.4
0.2
0.2
0.0
NM1=0.977901
0.0
2.5
2.0
1.5
1.0
0.5
0.0
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0
Separation
Separation
(g) 2d nc-3,,
(h) 2d- no4- &e
Figure 13: Normalized Mutual Information for approximate Pareto curves. The highlighted points show the solutions on the curve with highest values.
47

---

Measures nice k-means++
Variance
Measures
Variance
iris k-means++
1.4400e-08
RI
1.6864c-04
F1
6.6097c-09
5.0690e-04
F2
1.7680c-05
F2
6.6097c-09
FO.5
6.0840c-09
FO.5
1.1936e-04
NMI
3.4781e-04
NMI
4.5369e-08
rice k-means+
k-mcans++ k=7
RI
1.4400c-08
RI
1.2151e-03
F1
1.9033c-03
FI
6.6097e-09
F2
6.6097e-09
F2
8.0220c-04
PO.5
6.0840e-09
FO.5
2.5604e-03
NMI
1.3560c-03
NMI
4.5369c-08
iris Pareto
rice Pareto set
RI
8.9365c-04
RI
0.0000c+00
8.0365c-04
0.0000e+00
F2
0.4472c-04
0.0000=+00
FO.5
5.6302e-04
PO.S
1.2326e-32
NMI
1.1630c-03
NMI
1.1937e-06
dry-bean k-means++
wine k-mcans++
RI
1,887c-007
4.9972c-05
FI
2.2125c-05
FI
6.3148e-07
F2
5,2971c-05
F2
3.6481e-06
FO.5
6.8142c-06
FO.5
1.6959e-04
NMI
7.2917c-06
NMI
2.5335e-06
dry-bean k-means++ k=2
wine k-means++ k=3
RI
14560e-05
1.547lc-04
2.5828c-05
FI
1.2263e-03
F2
3.4703c-04
F2
1.3653e-04
FO,5
2.0610e-04
FO.5
1.432ee-03
NMI
1.7967c-05
1.9449e-05
dry-hean Pareto sel
wine Pareto
RI
1.9592c-05
RI
6.6312c-07
Fl
1.7173e-05
FI
2.5850e-05
F2
1 1.0253e-04
F2
9.2865e-05
3.5594c-05
FO.5
8,4455c-05
NMI
5.7523e-07
NMI
4.8492e-05
opidigits k-means++
20-10c-no3
k-rnanss++
RI
1.3865e-05
RI
4.4768c-05
0.2189e-04
F1
8.5650e-04
F2
6.0707e-04
F2
7.6900c-04
FO.5
2.8317e-04
FO.5
3.4128c-04
NMI
9.0615e-05
NMI
1.3592e-04
opidigits k-means++
2d-1 10c-no3 k-meuns++ k=7
RI
1.2933e-04
2.0670e-04
F1
1 1.8262e-03
Fl
1.7448c-03
F2
1.3216e-03
F2
1.3333c-03
FO.5
1.9015e-03
FO.5
2.0250c-03
NMI
5.6838e-04
NMI
4.3568e-04
optdigits Parcto set
2d- 10--03 sel
RI
2.8145e-05
RI
2.2066e-06
3.1205c-04
Fl
4.8728c-05
F2
2.5979c-01
F2
2.4905c-05
FO.5
1 1.6697--04
FO.5
6.8946e-05
NMI
1.134cc004
NMI
1.4273e-05
2d-4c-no3 k-mcans++
2d- 20-10c-no4 k-means++
RI
3.8151c-07
RI
2,1759e-05
Fl
6.1481c-07
Fl
3.4336e-04
F2
6.2162e-07
1.4351c-04
FO.5
5,5008c-07
FO.5
1.8235c-04
NMI
5.9403c-06
NMI
8.8342e-05
2d-4-no3 k-means++ k=
2d- 10c-no4
k-means++ k=4
RI
3.8151c-07
RI
5.9045e-05
6.1481c-07
FI
8.7161e-04
F2
6.2162e-07
F2
5.6323e-04
FO.5
5,5008c-07
FO.5
1.1198c-03
NMI
5.9403c-06
NMI
2.1481c-04
2d-4c-no3 Pareto
2d-10c-no4 Pareto set
RI
4.9304c-32
RI
4.4955c-05
Fl
1.2326c-32
Fi
5.5125e-04
F2
4.9304c-32
F2
1.3260e-04
FO.5
1.2326e-32
FO.5
4.5889c-04
NMI
1.2326e-32
NMI
7.0230e-05
Figure 14: Variance of values for 20 runs of k-means++ and our algorithm.
48

---

C.2 Visualizing median incomes in Germany
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 [6] 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 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 TubfigureTT9bltee together districts that are far apart. In Subfigure 196 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 very good idea how the incomes differ in different regions of Germany. This is also interesting because the geographic radius of this clustering 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 the clusters appear to be reasonable and meaningful.
To get 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 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 clustering districts with very different
different levels. On the other hand, in the geography-basee 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 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 321E. Indeed one can observe that in the map which colors the clusters according to their average median income lot more details are visible. However at the same time, the clusters are lot less compact often being split up into multiple regions or having holes 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 region.
49

---

4500
4000
3500
3250
3000
Figure 15: Visualization of the median monthly incomes in Germany (in Euro).
1200
Pareto Points
Income Difference in C
1000
800
600
400
200
150
200
250
300
350
400
450
500
550
Distance in km
Figure 16: The resulting Pareto curve for & = 16. The 10-th and 15-th solution are marked with red squares.
50

---

1600
Income Difference in G
1200
Pareto Points
1400
1000
1200
600
600
400
200
200
250
300
350
400
450
500
550
150
200
250
300
350
400
450
500
550
Distance In km
Distance in km
(a) l:
15
1200
Income Difference
600
400
200
100
200
300
400
500
600
Distance in km
(c) 20
Figure 17: The resulting Pareto curves for different A:
Income-based clustering
(b) The 10-th Pareto solution
(c) Geography- based clustering
Comparison between the 10-th Pareto solution with the purely geographic and the purely income based clustering for 1: 16.
Figure 18:
Resources and running time. The experiments were performed machine with 1.8 GHz Intel Core i7-8565U processor and 16 GB RAM. The source codes are in Java and were compiled using oracle OpenJDK version 21.02 The computations of the Pareto sets took most couple of seconds.
51

---

300
(4) Income-based clustering 16
400
111
(b) The 10-th Pareto solution
(c) Geography- -based clustering
Figure 19: Comparison between the 10-th Pareto solution with the purely geographic and the purely income-based clustering for à = 16. The clusters once colored according the average income over districts in that cluster (left) and once with well distinguishable colors (right).
52

---

193
(a) Clusters colored by the average income
(b) Clusters colored by well distinguishable colors
the districts
Figure 20: The 15-th Pareto solution for k: 16.
C.3 Clustering of sea level data
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 coastlines. Figure 21 shows their positions. Each of those stations measures the sea level its respective location on 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 representative set of stations, that uses fewer stations, but does not loose lot of information. It might also be helpful in order to achieve more evenly spread out set of stations since the northern hemisphere is over-represented in terms of concentration of the stations in comparison 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
Figure 21: Positions of the PSMSL tide gauge stations.
53

---

Pareto Points
0.18
Mean Time Series Distance in m
0.16
0.12
0.10
0.06
2000
4000
6000
0000
Euclidean Distance km
Figure 22: Approximate Pareto curve for the sea level data for k=150. The 54-th approximate Pareto solution is highlighted in red.
over the pairwise difference between two time series, namely
1 7 Σ 1 - (2) Σ
dmean
where {(1), {(2) are two time series with |e(0)= 22 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 crucial part of our analysis, we conducted our experiments on synthetic dataset using the ORAS5 [8] global ocean reanalysis, which simulates the sea level beginning in 1958 until today grid coordinates all around the world. We created time series similar to the PSMSL dataset by mapping the coordinates of every station to the gcographically 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 level height, normalized all time series by subtracting their mean value.
We considered the clustering for & 150. In total, the approximate Pareto 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 highlighted in red, since we are using it in later figures as example for 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 be major improvements 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.
metric while the loss the other metric is relatively
In the following, we will compare the 54-th Pareto solution the clusterings, that either only consider the time series based clustering, only consider the geography based clustering. The clusterings we compare have been computed without any knowledge 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 located on the middle of the Pareto curve and therefore should be good trade-off between the different objectives.
54

---

Table Comparison between the time series based clustering, geography based clustering and the 54-th Pareto clustering with regard to the biggest cluster radius for both metrics, the mean cluster radius over all clusters for both metrics, and the max. cluster size (cs). The values for the time series based metrics (ts) are in and rounded to three decimals, the geographic distances (geo) are in km and rounded two decimals.
max geo
mean geo
mean
Geography based clustering
1,566.48
619.40
0.209
0,041
95
54-th Pareto Solution Time Series based clustering
2,411.21
799.05
0,080
0,031
128
18,172.36
1,570.64
0.067
0.028
157
One can see visualization of the three clusterings in Figure 23 For more details, Figure 24 shows the region of Europe (since there is high concentration 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 very high concentration of stations usually also contain more cluster centers than the regions with low concentration of cluster centers, while in the Pareto solution and especially in the geography based clustering, the centers 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. 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 the time series based clustering span over three different oceans.
Analogously, Figure 25 shows the worst cluster with respect 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 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.
only restricted the worst
Resources and running time. The experiments were performed on machine with an 2,4 GHz Apple M2 processor and 24 GB RAM. The source codes are Java and were compiled using oracle OpenJDK version 21.02. The computations of the Pareto sets took less than minute.
55

---

(a) Geography based clustering.
(b) The 54-th Pareto solution.
(c) Time series based clustering.
Figure 23: The geographically biggest clusters of the 54-th Pareto solution, the clustering that only considers the geographic distance, and the clustering that only considers the time series for k 150. Different clusters are depicted in different colors. The centers of clusters are marked by red square.
56

---

Geography based clustering.
(b) The 54-th Pareto solution.
(c) Time series based clustering.
Figure 24: The geography based clustering, the 54-th Pareto solution, and the time series based clustering in the area of Europe. Centers are drawn in red.
forndiee Sea loyd nagit k
2.4
0.0
nomaiteed
-0.-
2000
20:00
15:00
1900
2000
2010
2020
2040
1070
1000
2000
2000
2020
(a) Geography based clustering.
(b) The 54-th Pareto solution.
Normalzed 56a Lovel Holght in m.
0.2
13500
12520
12:00
22730
2010
2020
(c) Time series based clustering.
Figure 25: Comparison between the worst clusters (for the time series based distance function) of the 54-th Pareto solution, the clustering that only considers the geographic distance, and the clustering that only considers the time series for k 150. The centers of the clusters are marked red.
57

---

Geography based clustering.
(b) The 54-th Pareto solution.
(c) Time series based clustering.
Figure 26: Comparison between the geographically worst cluster of the 54-th Pareto solution with the clustering that only considers the geographic distance and the clustering that only considers the time series for = 150. The centers of the clusters are marked by a red square.
58

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction state that we provide algorithms for approxi- mating Pareto sets, achieve provable approximation guarantees and perform experiments. All theoretical results supporting the first two claims are then summarized in Section 2 in particular the main guarantees and the theorems proving them are listed in Table 2 and 3 The experimental evaluation is summarized in Section
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
We try to be precise as possible when stating the results. One limitation is that we restrict the choice of centers the point set. This is stated on 2 (paragraph Objectives). Another limitation is that the distance function has to be metric, but this is common for all the mentioned clustering objectives.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
59

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
The theoretical results are an integral part of this paper. Due to space con- straints, we could not include the technical proofs into the main part. We have decided to present the full derivation of the material in the supplementary material. Results involving the k-separation problem in Section B in the supplementary material and Section A contains all results combining minimization objectives.
Justification:
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The algorithms to compute approximate Pareto sets which are discussed in the theoretical part of this paper were implemented for the combinations k-center with k-center and k-separation with k-means. In the latter case the implemented algorithm differs in some aspects from the algorithm described in Section A.3 for practical reasons. The differences discussed in Section C.1 For the evaluation of the results we provide detailed description of the evaluation process along with a description of the used measures in Section C.I
Justification:
We provide the source code via GitHub repository /https://ttthh:ht: cww.coo/aaaaa// aaammalgoo-n ahgo-hhu/ paretoClustering All data sets are from publicly available sources and we provide links to those sources, see Table and the references in Section 3.2
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
60

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should descrihe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided the code and referenced the sites where the data can be obtained. The code is in Java C++ and does need specific environment to be compiled and run. The data used Section [.. has not been pre-processed except for reading the ground truth from the file into separate file. For the data in Section C.2 the data is publicly available
and straightforward to use. The sea level data used in Section C.3 might be more of challenge. We tried describe the process to enable reproduction. We would like to publish the pre-processed data set, but we are worried about copyright issues if we re-post the data. Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co.
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nipp.co. wttpccccpppccccceecee. httpr//guudeeeeeeeuuueeieeeeeeee Coooeeoooiisssseeeeceo ssinnooiccyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our experimental evaluation does not include training phase. The aim of the experiments is to demonstrate the usefulness our theoretical findings on Pareto sets for clustering problems. The measures used in the results are explained and there are no hidden parameters (the only parameter that our algorithms have is the number A of centers, and this is specified in the experimental sections).
61

---

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 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.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 [4
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, confi- dence 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 clearly stated (for example, train/test split, initialization, random drawing of some parameter, 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.
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 96% CI, if the hypothesis of Normality 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 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Most experiments were executed 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 well giving reasonable bound the time of execution.
Guidelines:
The answer NA means that the paper does 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 the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
62

---

9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: While one can never predict entirely the applications of ones research, there is no straightforward way to use the results for any harmful applications. Furthermore to the authors' knowledge the used data sets are open access and can be used for purposes similar to this one.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: To the authors' knowledge this work will not affect society directly. Our algorithms can be used obtain better clusterings.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: None of our data models have this kind of risk.
Guidelines:
The answer NA means that the paper poses such risks.
63

---

Released models that have 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 URI
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, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if 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
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
The main assets introduced in this paper are the algorithms which are described and analyzed thoroughly in the respective sections.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model 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.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
64

---

Justification:
There were no crowdsourcing experiments or something similar.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The question is not applicable to our research.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
65


Reviews:
[{"review_id": "vs8ppzVEIE", "reviewer": "Reviewer_CrwW", "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.", "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?\n\nPareto-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?\n\nThe 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": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses the complex issue of multi-objective clustering. The motivation with k-diameter and k-separation problems accurately captures the difficulty of optimizing multi-objective optimization settings. The work provides a novel solution to approximate the Pareto front for bi-objective k-clustering problems.\n2. The authors validate their approach through extensive experiments, showing that the approximate Pareto front includes superior clustering compared to those obtained by single-objective methods.\n3. The paper has been written very well with detailed approaches.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*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.*\n\nThe main novelty is that algorithms with theoretical guarantees for the computation of Pareto sets for clustering have not been studied before (the only known related result was developed in a different framing). We give many results matching the best single-objective approximation ratios, and (nearly) none of this was known beforehand.\n\nGiven that better bi-objective guarantees would also correspond to better single-objective approximations and most of these clustering problems are well studied, we find it unlikely that we could get any further improvements in these cases. We are aware that at some points our bi-objective algorithms are pretty straightforward adaptions of existing algorithms but we felt that it still makes sense to include these results for completeness. Rather than calling one single algorithm the main result we would consider the sum of all techniques presented in this paper to deal with all the different combinations of objective functions, as well as the given worst case instances and the experiments, our contribution to a natural research question that has only been studied scarcely before.\n\nIndeed Sec. 2.1 has less to offer in terms of technical contribution in comparison to the other sections. We put it in front because we like the conceptual contribution as it offers a new angle to the very basic question of how to obtain a meaningful clustering that reconciles two natural ideas (separation and compactness of clusters).\n\n*Weakness 2 / Question 1+3 (Technical contribution) 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?*, also *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.*\n\nThe refered line 229 did actually not require much change in techniques. Here is a list of novel contributions of technical nature:\n- the runtime reduction technique in A.1. The main idea to achieve the improvement was to not calculate an entirely new graph and independent set in every iteration of Hochbaum and Shmoys but rather to modify the already existing datastructures. Via the careful usage of a potential function we were able to prove the reduced runtime of $O(n^3)$ (pages 14-16)\n- the lower bound for the size of the Pareto set for k-center/k-center in A.2 (page 17)\n- using nesting for the k-sep/k-median case (Lemma 41/45)\n- lower bound for the size of the Pareto set for k-median and k-means (Theorem 21)\n- lower bound examples showing that SL cannot be reasonably approximated together with the other objectives (Ex. 1, Ex. 31, Obs. 36, Obs. 46, )\n- the algorithm in C.1 is also novel (but relatively straightforward)\n\nAside from this we believe that collecting many techniques and finding those that can be applied in this setting is a contribution in its own right, like using nesting from hierarchical clustering (Lemma 41/45) or observing that Diakonikolas' framework works well with approximation algorithms. \n\nFinally, Sec. C.2 and C.3 offer novel modeling for two real world problems to highlight the usage of bi-objective optimization algorithms. \n\n*Q2-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?*\n\nAs we have shown in Ex. 1, Ex. 31, Obs. 36 and Obs. 46, at least for the combination of the k-separation objective with any other clustering objective we cannot hope for any bi-criteria approximation guarantee even if both objectives are defined on the same metric. Similarly it can be shown that it is not possible to optimize k-means or k-median and k-center or k-diameter at the same time since the k-center/diameter objective could force the algorithm to pick outliers which might decrease the quality of the means/median solution by an arbitrary amount (e.g., combining k-center/diameter with k-means/median, one would construct two point sets of high cardinality close to each other and one single point far away. For $k=2$, kmeans/median has to place one point in each large point set while k-center would spend one center for the outlier.) Thus, bi-criteria guarantees are in some sense the best we can hope for in this setting (at least for polynomial-time algoirthms).\n\nWe are not sure if we understood the question correctly. If it is about the fact that we have two objectives rather then many, then we instead remark that we are definitely interested in the extension to multiple objectives, and in many cases, it should be possible. But the paper is already very long, so we left including additional technical work for multiple objectives to future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QoB73Z4snd", "reviewer": "Reviewer_Xxjr", "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.", "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.\n\nQ2: 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.\n\nQ3: Can the authors provide more detailed real-world applications where these bi-objective clustering algorithms would be particularly beneficial? \n\nQ4: 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": "This paper is mainly a theoretical result, and there is no negative societal impact.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The authors give a novel approximately pareto-optimal approach for bi-objective k-clustering problems.The authors gives the results for combining k-separation with various objectives with (1,\\alpha) approximate Pareto set with respect to sep with metric d_1 and f_2 with metric d_2. \n\n2. The paper produces an informative ensemble. These algorithms achieve provable approximation guarantee. The theoretical evidence are solid and the experiments are well-established.\n\n3. The authors verify that the approximate pareto front contains good clustering which cannot be found by considering a single objective.", "weaknesses": "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.\n\n2. 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.\n\n3. The algorithms have polynomial running time. As far as we know, the pareto optimization of other problems can be done in linear time.\n\n4. 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.\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*W1: 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.*\n\nWe chose these objectives since they are the most known classical partitional clustering objectives and it seems useful to know about their joined optimization. Indeed, we originally were motivated by hoping for algorithms that could simultaneaously approximate several objectives until we proved that this was not possible. \nFrom a practical point, our original motivation stemed from applications C.2 and C.3. In collaborations we observed the need to find clusterings while optimizing over two very different metrics, e.g., one based on Euclidean distances and one based on time series similarity. We believe that such trade-offs are quite natural in practical applications.\n\n*W2: 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.*\n\nWe did indeed not implement a super fast k-means++ variant. There are several options to do so, but they require additional work to satisfy theoretical guarantees. Notice that it is not sufficient to simply pick a fast k-means algorithm where it is not clear how to bound the second objective. In C.1 we go a middle ground by using k-means++ instead of the primal dual algorithm used in A.3 (this change decreases the approximation ratio but the algorithm still satisfies weaker guarantees). The k-means++ algorithm is state-of-the art for medium sized data. We have speculatd about the case of large data quite a bit and believe that super fast combinations are also possible, but the aim of this paper was an initial (and already pretty page-heavy) collection of first results on the topic. \n\n*W3: The algorithms have polynomial running time. As far as we know, the pareto optimization of other problems can be done in linear time.*\n\nFor clustering problems as k-center and k-means, there are no algorithms which obtain constant factor approximations and have linear running time even in the case where we optimize over a single objective. Therefore we conjecture that it is not possible to compute a pareto set or an approximate pareto set in linear time since it requires solving multiple such problems. Our experiments can be seen as proof of concept that the approaches can be practical and work on medium size data sets.\n\n*W4 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.*\n\nAnswer: We apologize for the more technical nature of the appendix. We agree that the exposition could be better and plan to improve it for a long version of the paper. We hope that this comment did not apply to the main part of the paper. We welcome any additional pointers to sections that were unclear in order to improve them.\n\n*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.*\n\nWe apply the standard definitions for Pareto sets to the setting where the aim is to optimize two clustering objectives. The fact that we also include the possibility to optimize over two different metrics is due to the application in C.3 where this is necessary.\n\n*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.*\n\nSL may be over-highlighted in the introduction. We actually consider two angles: i) Combining single linkage with other objectives and ii) combining various well-known partitional clustering objectives with each other. For i), our motivation was of a more conceptual nature, to see if we can improve clustering for finding ground truths by including separation constraints into the consideration. ii) is directly motivated by applications where two different metrics are present. \n\n\"Q3: Can the authors provide more detailed real-world applications where these bi-objective clustering algorithms would be particularly beneficial?\"\n\nWe point out that the data in C.2 and C.3 are from real-world applications. In particular C.3 is a question that is actually studied in geodesy and where two metrics are present over which one needs to optimize. Could you clarify in which aspect more details would be required? It may be that we described the applications a bit too short in the main body of the paper, and we apologize for that. \n\n\"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.\"\n\nIn C.1 we focus on the question whether the combination of two clustering objectives can improve the quality of a solution. Thus our experiments provide a comparison between the quality of a clustering obtained by k-means++,  a Single Linkage clustering, and the best clustering on the pareto curve. In C.2 and C.3 our aim was to highlight the usefulness of bi-objective clustering. We did not optimize the implementation for speed. Improving our implementation speed-wise or extending our guarantees to faster algorithms is an interesting open question. We also think that the computation of the full Pareto set can in most cases be avoided by identifying a smaller set of interesting solutions automatically, but we did not yet test this approach.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yz7mz2Qyqz", "reviewer": "Reviewer_2DdM", "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).  \n\nTwo 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.\n\nThorough 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.", "questions": "See weaknesses.", "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "+ This paper is well written and easy to follow.\n\n+ The multi-objective clustering problem is valuable and important for many real-world applications. This work would be impactful and inspire many follow-up work on this research direction.\n\n+ The proposed algorithms and their corresponding theoretical analysis are comprehensive and cover a wide range of different problem settings in a systematic way, which is a solid contribution.\n\n+ The experiments are well-designed to nicely show the benefits of multi-objective clustering.", "weaknesses": "I enjoy reading this paper and do not see any obvious weakness of this work. Below are some minor concerns and questions.\n\n**1. Centers Chosen from the Point Set** \n\nOne 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. \n\nHowever, 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? \n\n**2. Extension of the LP Rounding Algorithm**\n\nAs 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.\n\nIn 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?\n\n**3. Generalization to more than Two Objectives**\n\nThis 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?\n\n**4. Minimum Cardinality Set**\n\nIt 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)? \n\n**5. Finding the Most Suitable Solution**\n\nThe 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?\n\nIn addition, how can the clustering number $k$ be properly chosen for real-world multi-objective clustering problems?\n\n**6. Order of the Problem Settings**\n\nThere 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?\n\n**7. Publication Venue**\n\n*(This part will not affect my decision.)*\n\nThis 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. \n\nI think a journal like JMLR should be a more suitable choice to publish this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*1. Centers Chosen from the Point Set*\n\nWe decided to restrict to this case in the theory part. In 2.1 we could switch to choosing centers from a larger space, e.g., the infinite metric space $R^d$ because this algorithm is still a 2-approximation even if this case. It would make even more sense to switch for k-means (in the practical algorithm in C.1 we actually compute centers from $R^d$.). But e.g. in 2.2, if we would allow $R^d$ for one objective we can not use standard R^d techniques like epsilon-nets unless both objectives use $R^d$. On the other hand, all our results imply results for the infinite case with an additional factor of 2, so we opted against including more case distinctions. We agree that this is not sufficiently discussed in the introduction yet.\n\n*2. Extension of the LP Rounding Algorithm*\n\nWe did not try to adapt the algorithm by Charikar et al. But in the single objective case, it is actually the JV algorithm that is often adapted, while the rounding algorithm (which is actually older than the JV algorithm) involves many intricate steps and we are not aware of many adaptations. For example, the (3+eps)-k-msr-approximation is based on the JV algorithm. We are not even sure if the Alamdari/Shmoys algorithm can be adapted to the case of different metrics which they did not consider (it works for two objectives on the same metric). Which other setting would you be interested to know about? \n\nPro/Cons: The incomparable approximation factor may be even in favor of Alamdari/Smoys. But we expect that our algorithm is better suited for practical purposes. We had positive experiences with implementations of other JV adaptations in the past. We did not write anything about this because we did not practically test it here. Finally, the algorithm by Charikar et al. requires actually solving an LP, while the primal dual algorithm is combinatorial (only the proof needs the LP), which could also be a pro of our algorithm.\n\n*3. Generalization to more than Two Objectives*\n\nFor the sake of simplicity we focus on the combination of two objectives. We believe that the cases where we combine at most one k-median or k-means objective with other (possibly multiple) objectives as k-center/k-diameter/k-separation can be carried out with techniques similar to the ones presented in this work. The combination of two k-median/k-means objectives differs substantially from the other combinations since we are only able to compute an approximation to the convex pareto set. As long as one only uses sum based objectives (k-median or k-means), this approach should also extend to more than two objectives.\nOne may adapt the primal dual algorithm by Jain and Vazirani where we change the objective to a convex combination of multiple k-median/k-means objectives and combine it with (multiple) k-center objectives to compute an approximation to the convex pareto set. \n\nFrom a practical point of view the main downside of computing the pareto set for multiple objectives lies in the large size of the pareto set and therefore also in the high running time. This only seems to make sense when combined with autmatic methods to identify an interesting subset of the approximate Pareto set that we want to compute.\n\n*4. Minimum Cardinality Set*\n\nThis is an interesting question that we did not consider yet. Diakonikolas (2011) and Vassilvitskii, Yannakakis (2005) both show that the smallest approximate Pareto set can be approximated for large groups of problems, namely if you have a polynomial time gap routine (VY2005) or if you can solve a restricted version of the problem in polynomial time (D2011). Unfortunately, those frameworks do not directly carry over to our setting, since we generally only have constant factor approximations for the gap problem. It seems possibly that these frameworks could be adapted to work in this context as well. \nIt would be also interesting to check if our algorithms can be adapted directly to compute smaller appr. Pareto sets for example for the combination of two k-center objectives if one really has to consider all combinations or can cleverly skip certain values that are already 2-approximated. \n\n*5. Finding the Most Suitable Solution*\n\nIndeed we originally thought of this as an ensemble which is then checked manually. However, it clearly makes sense to combine the algorithms with known techniques to choose k (elbow method, more complicated phase transistioning detections), or to extend these methods to compute an \"interesting\" subset of the Pareto curve, or to apply other techniques to reduce the size of the approximate Pareto set (also related to question 4). In case of applications C.1, C.2 and C.3 the number of solutions was managable manually. \n\nIn C.1 we observed a general trend that small separation values improve the solution while enforcing a large separation did not help. It seems that the reason is that k-means++ sometimes splits large clusters in the middle and this is not possible when close points are forced to be in the same cluster. So for practical applications as a rule of thumb one could compute the first few clusterings (which have small separation and small k-means cost) on the Pareto curve and select one of them manually. Only computing this part of the curve of course also reduces the running time.\n\n*6. Order of the Problem Settings*\n\nThis is just an oversight and has no hidden meaning. Thank you for pointing it out!\n\n*7. Publication Venue*\n\nThank you very much for pointing out the comprehensive nature of our paper. It is true that it does not really fit into the page limit and we struggled to present all material to the extend that we would have liked to. We chose to sent the paper to NeurIPS  since we introduce a new angle to the study of approximation algorithms for clustering. We believe that it would be an interesting contribution to NeurIPS since there are many possible follow-up questions to obtain faster and better approximations of the Pareto curves.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for considering our work and providing detailed reviews. Replies to remarks and questions can be found in the individual rebuttals for each review.

Meta-review: 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.
Decision: Accept (poster)