Metric Perturbation Resilience

arXiv:1607.06442v1 [] 21 Jul 2016

Konstantin Makarychev
Microsoft Research

Yury Makarychev∗
TTIC

Abstract
We study the notion of perturbation resilience introduced by Bilu and Linial (2010) and
Awasthi, Blum, and Sheffet (2012). A clustering problem is α-perturbation resilient if the
optimal clustering does not change when we perturb all distances by a factor of at most α.
We consider a class of clustering problems with center-based objectives, which includes such
problems as k-means, k-median, and k-center, and give an exact algorithm for clustering 2perturbation resilient instances. Our result improves
upon the result of Balcan and Liang
√
(2016), who gave an algorithm for clustering 1 + 2 ≈ 2.41 perturbation resilient instances.
Our result is tight in the sense that no polynomial-time algorithm can solve (2 − ε)-perturbation
resilient instances unless N P = RP , as was shown by Balcan, Haghtalab, and White (2016).
We show that the algorithm works on instances satisfying a slightly weaker and more natural
condition than perturbation resilience, which we call metric perturbation resilience.
∗

Supported by NSF CAREER award CCF-1150062 and NSF award IIS-1302662.

1

Introduction

In this paper, we present an exact algorithm for solving 2-perturbation resilient instances of clustering problems with natural center-based objectives. The notion of perturbation resilience was
proposed by Bilu and Linial [5] and Awasthi, Blum, and Sheffet [1]. Informally, an instance is
perturbation resilient if the optimal solution does not change when we perturb the instance. The
definition was introduced in the context of beyond-the-worst-case analysis and aims to capture
a wide class of real-life instances that are computationally easier than worst-case instances. As
several authors argue, in instances arising in practice, the optimal solution is often significantly
better than all other solutions and thus does not change if we slightly perturb the instance [5, 4]. It
was shown that perturbation resilient instances of such problems as k-center, k-means, k-median,
clustering problems with center-based and min-sum objectives, Max Cut, Minimum Multiway Cut,
and TSP (with a sufficiently large value of the resilience parameter) can be solved exactly in
polynomial-time [1, 2, 3, 4, 5, 6, 7]; while the worst-case instances of these problems are NP-hard.
In a clustering problem, we are given a metric space (X, d) and an integer parameter k; our goal
is to partition X into k clusters C1 , . . . , Ck so as to minimize the objective function H(C1 , . . . , Ck ; d)
(which depends on the problem at hand). The most well-studied and, perhaps, most interesting
clustering objectives are k-means, k-median, and k-center. These objectives are defined as follows.
Given a clustering C1 , . . . , Ck , the objective is equal to the minimum over all choices of centers
c1 ∈ C1 ,. . . ,ck ∈ Ck of the following functions:
Hmeans (C1 , . . . , Ck ; d) =

k X
X

d(u, ci )2 ;

Hmedian (C1 , . . . , Ck ; d) =

k X
X

d(u, ci );

Hcenter (C1 , . . . , Ck ; d) =

i=1 u∈Ci

i=1 u∈Ci

max max d(u, ci ).

i∈{1,...,k} u∈Ci

Note that in the optimal solution each cluster Ci consists of those vertices u that are closer to ci
than to other centers cj ; i.e. (C1 , . . . , Ck ) is the Voronoi partition of X with centers c1 , . . . , ck .
We refer to objectives satisfying this property as center-based objectives. We study two closely
related classes of center-based objectives – separable center-based objectives and natural centerbased objectives (which we discuss below and formally define in Section 2). We note that k-means,
k-median, and k-center are separable and natural center-based objectives. Now we formally define
perturbation resilience.
Definition 1.1. Consider an instance I = ((X, d), H, k) of a clustering problem on a metric space
(X, d) with objective H. An instance ((X, d′ ), H, k) is an α-perturbation of I if
d(u, v) ≤ d′ (u, v) ≤ αd(u, v)

for every u, v ∈ X;

here, d′ does not have to be a metric. An instance I is α-perturbation resilient if every αperturbation of I has the same optimal clustering as I. We will refer to α as the perturbation
resilience parameter.
This definition does not require that the perturbation d′ is a metric (d′ does not have to satisfy
the triangle inequality). It is more natural to consider only metric perturbations of I — those
perturbations in which d′ is a metric. In this paper, we give the definition of metric perturbation
resilience, in which we do require that d′ is a metric (see Definition 2.4). (Every α-perturbation
resilient instance is also α-metric perturbation resilient.)
1

Known results. Awasthi, Blum, and Sheffet [1] initiated the study of perturbation resilient
instances of clustering problems. They offered the definition of a separable center-based objective (s.c.b.o.) and introduced an important center proximity property (see Definition 2.5). They
presented an exact algorithm for solving 3-perturbation
resilient instances of clustering problems
√
with s.c.b.o.; they also gave an algorithm for (2 + 3)-perturbation resilient instances of clustering
problems with s.c.b.o. that have Steiner points. Additionally, they showed that α-perturbation
resilient instances of k-median with Steiner points
are N P -hard when α < 3. Later, Balcan and
√
Liang [3] designed an exact algorithm for (1 + 2)-perturbation resilient instances of problems with
s.c.b.o., improving the result of Awasthi, Blum, and Sheffet. Balcan and Liang also studied clustering with the min-sum objective and (α, ε)-perturbation resilience (a weaker notion of perturbation
resilience, which we do not discuss in this paper). Recently, Balcan, Haghtalab, and White [2]
designed an algorithm for 2-perturbation resilient instances of symmetric and asymmetric k-center
and showed that there is no polynomial-time algorithm for (2 − ε) perturbation resilience instances
unless N P = RP . They also gave an algorithm for 2-perturbation resilient instances of problems
with s.c.b.o. satisfying a strong additional condition of cluster verifiability.
√ To summarize, the best
known algorithm for arbitrary s.c.b.o. requires that the instance be 1 + 2 ≈ 2.4142 perturbation
resilient [3]; the best known algorithm for k-center requires that the instance be 2-perturbation
resilient, and this result cannot be improved [2].
We refer the reader to [6] for an overview of known results for stable instances of combinatorial
optimization problems.
Our results. We define a class of clustering problems with natural center-based objectives; an
objective is a natural center-based objective if it is representable in the following form. For some
functions fc and gu (r) (fc is a function of c, gu (r) is a function of u and r; intuitively, fci is the
cost of having a center at ci and gu (r) is the cost of connecting u to a center at distance r from u),
we have
k 

X
X
fci +
gu (d(u, ci )) ,
H(C1 , . . . , Ck ; d) = min
ci ∈Ci

or
H(C1 , . . . , Ck ; d) = min max
ci ∈Ci

i=1



u∈Ci


max fci , max gu (d(u, ci )) .

i∈{1,...,k}

i∈{1,...,k}
u∈Ci

This class includes such problems as k-center, k-means, k-median, and metric facility location (for
the first three problems: fc = 0 and gu (r) equals r 2 , r, and r respectively).
We present a polynomial-time algorithm for 2-metric perturbation resilient instances of clustering problems with natural center based objectives;√thus, we improve the known requirement on the
perturbation resilience parameter α from α ≥ 1 + 2 ≈ 2.4142 to α ≥ 2 and relax the condition on
instances from a stronger α-perturbation resilience condition to a weaker and more natural α-metric
perturbation resilience condition. Our result is optimal, since even (2 − ε)-perturbation resilient
instances of k-center cannot be solved in polynomial time unless N P = RP
√ [2]. In particular, our
result improves the requirement for k-median and k-means from α ≥ 1 + 2 to α ≥ 2.
Theorem 1.2. There exists a polynomial-time algorithm that given any 2-metric perturbation
resilient instance ((X, d), H, k) of a clustering problem with natural center-based objective, returns
the (exact) optimal clustering of X.
Our algorithm is quite simple. It first runs the single-linkage algorithm to construct the minimum spanning tree on points of X and then partitions the minimum spanning tree into k clusters
2

using dynamic programming. We note that Awasthi, Blum, and Sheffet [1] also used the singlelinkage algorithm together with dynamic programming to cluster 3-perturbation resilient instances.
However, their approach is substantially different from ours: They first find a hierarchical clustering
of X using the single-linkage algorithm and then pick k optimal clusters from this hierarchical clustering. This approach fails for α-perturbation resilient instances with α < 3 (see [1]). That is why,
we do not use the single-linkage hierarchical clustering in our algorithm, and, instead, partition the
minimum spanning tree.
We note that the definitions of separable and natural center-based objectives are different.
However, in Section 5 we consider a slightly strengthened definition of s.c.b.o. and show that every
s.c.b.o., under this new definition, is also a natural center-based objective; thus, our result applies
to it. We are not aware of any non-pathological objective that satisfies the definition of s.c.b.o. but
is not a natural center-based objective.
Finally, we consider clustering with s.c.b.o. and show that the optimal solution for every αmetric perturbation resilient instance satisfies the α-center proximity property; previously, that
was only known for α-perturbation resilient instances [1]. Our result implies that the algorithms
by Balcan and Liang [3] and Balcan, Haghtalab, and White [2] for clustering with s.c.b.o. and
k-center, respectively, apply not only to α-perturbation resilient but also α-metric perturbation
resilient instances.
Overview. In Section 2, we formally define key notions used in this paper. Then, in Section 3,
we prove that the optimal solution for every α-metric perturbation resilient instance satisfies the
α-center proximity property. We use this result later in the analysis of our algorithm; also, as we
noted above, it is of independent interest and implies that previously known algorithms from [2, 3]
work under the metric permutation resilience assumption. In Section 4, we present our algorithm
for solving 2-perturbation resilient instances of problems with natural center-based objectives. The
algorithm consists of two steps. In the first step, we find a minimum spanning tree in the metric
space (X, d). In the second step, we partition the tree into k subtrees using dynamic programming
and then output the corresponding clustering of X. Finally, in Section 5, we prove that if a s.c.b.o.
satisfies some additional properties, then it is a natural center-based objective.

2

Preliminaries

In this section, we formally define key notions used in this paper: a clustering problem, α-metric
perturbation resilience, separable center-based and natural center-based objectives.
Definition 2.1. An instance of a clustering problem is the tuple ((X, d), H, k) of a metric space
(X, d), objective function H, and integer number k > 1. The objective H is a function that given
a partition of X into k sets C1 , . . . , Ck and a metric d on X returns a nonnegative real number,
which we call the cost of the partition.
Given an instance of a clustering problem ((X, d), H, k), our goal is to partition X into disjoint
sets C1 , . . . , Ck , so as to minimize H(C1 , . . . , Ck ; d). Now we define center-based and separable
center-based objectives. We note that the definitions of Awasthi et al. [1] make several implicit
assumptions that we make explicit here.
Definition 2.2. We say that H is a center-based objective function if the following properties hold.
1. Given a subset S ⊂ X and distance dS on S, we can find the optimal center c ∈ S for S, or, if
there is more than one choice of an optimal center, a set of optimal centers center(S, dS ) ⊂ S.
(In the former case, center(S, dS ) = {c}).
3

2. For every metric d on X, there exists an optimal clustering C1 , . . . , Ck of X (i.e., a clustering
that minimizes H(C1 , . . . , Ck ; d)) such that for every two distinct clusters Ci , Cj , every point
p in Ci and centers ci ∈ center(Ci , d|Ci ) and cj ∈ center(Cj , d|Cj ) we have d(p, ci ) ≤ d(p, cj ).
Furthermore, if the optimal clustering C1 , . . . , Ck is unique, then d(p, ci ) < d(p, cj ).
The objective is separable if, additionally, we can define individual cluster scores so that the following
holds.
• The cost of the clustering is either the sum (for separable sum-objectives) or maximum (for
separable max-objectives) of the cluster scores.
• The score H(C, d|C ) of each cluster C depends only on C and d|C , and can be computed in
polynomial time.
In this paper, we consider a slightly narrower class of natural center-based objectives (which
we described in the introduction). The class contains most important center-based objectives: kcenter, k-means, and k-median, as well as the facility location objective. We are not aware of any
reasonable center-based objective that is not a natural center-based objective. Now, we formally
define natural center-based objectives.
Definition 2.3. We say that H is a natural center-based objective function for a ground set X, if
there exist functions f : X → R and g : X × R → R such that
H(C1 , . . . , Ck ; d) = min

ci ∈Ci

or
H(C1 , . . . , Ck ; d) = min max
ci ∈Ci

k 

X
X
gu (d(u, ci )) ,
fci +
i=1



u∈Ci


max fci , max gu (d(u, ci )) .

i∈{1,...,k}

(1)

i∈{1,...,k}
u∈Ci

(2)

We require that the functions f and g be computable in polynomial time, and that gu be nondecreasing for every u ∈ X. We call points ci the centers of the clustering.
P
We could have also defined an objective with an ℓp -aggregate function H = ( ki=1 fcpi +

P
p 1/p , but it is equivalent to (1) with f ′ (c) = f p (c) and g ′ (u, r) = g p (u, r).
u∈Ci gu (d(u, ci ))
Now, we formally define a metric perturbation and metric perturbation resilience. Since we
do not require that the objective H is homogeneous as a function of the metric d, we introduce
two perturbation resilience parameters α1 and α2 in the definition, which specify by how much the
distances can be contracted and expanded, respectively, in the perturbed instances.
Definition 2.4. Consider a metric space (X, d). We say that a metric d′ is an (α1 , α2 )-metric per′
turbation of (X, d) if α−1
1 d(u, v) ≤ d (u, v) ≤ α2 d(u, v) for every u, v ∈ X. An instance ((X, d), H, k)
is (α1 , α2 )-metric perturbation resilient if for every (α1 , α2 )-metric perturbation d′ of d, the unique
optimal clustering for ((X, d′ ), H, k) is the same as for ((X, d′ ), H, k).
Note that the centers of clusters in the optimal solutions for ((X, d), H, k) and ((X, d′ ), H, k)
may differ. We say that an instance (H, (X, d), k) is α-metric perturbation resilient if it is (α, 1)metric perturbation resilient.
Observe that if instance ((X, d), H, k) is (α1 , α2 )-metric perturbation resilient, then ((X, λd), H, k)
is (λα1 , λα2 )-metric perturbation resilient for λ ∈ [α−1
1 , α2 ]. Particularly, if ((X, d), H, k) is (α1 , α2 )metric perturbation resilient, then ((X, α2 d), H, k) is (α, 1)-metric perturbation resilient and the
4

optimal solution for ((X, α2 d), H, k) is the same as for ((X, d), H, k). Thus, to solve an (α1 , α2 )metric perturbation resilient instance ((X, λd), H, k), it suffices to solve α = (α1 α2 ) metric perturbation resilient instance ((X, α2 d), H, k). Consequently, we will only consider α-metric perturbation
resilient instances in this paper.
Finally, we recall the definition of the α-center proximity property, introduced in [1].
Definition 2.5. We say that a clustering C1 , . . . , Ck of X with centers c1 , . . . , ck satisfies the
α-center proximity property if for all i 6= j and p ∈ Ci , we have d(p, cj ) > αd(p, ci ).

3

Center Proximity for Metric Perturbation Resilience

In this section, we prove that the (unique) optimal solution to an α-metric perturbation resilient
clustering problem satisfies the α-center proximity property. Our proof is similar to the proof of
Awasthi, Blum, and Sheffet, who showed that the optimal solution to a (non-metric) α-perturbation
resilient clustering problem satisfies the α-center proximity property.
Theorem 3.1. Consider an α-metric perturbation resilient clustering problem ((X, d), H, k) with
a center-based objective. Let C1 , . . . , Ck be the unique optimal solution; and let c1 , . . . , ck be a set
of centers of C1 , . . . , Ck (that is, each ci ∈ center(Ci , d|Ci )). Then, the following α-center proximity
property holds: for all i 6= j and p ∈ Ci , we have d(p, cj ) > αd(p, ci ).
Proof. Suppose that d(p, cj ) ≤ αd(p, ci ). Let r ∗ = d(p, ci ). Define a new metric d′ as follows.
Consider the complete graph on X. Assign length len(u, v) = d(u, v) to each edge (u, v) other than
(p, cj ). Assign length len(p, cj ) = r ∗ to the edge (p, cj ). Let metric d′ (u, v) be the shortest path
metric on the complete graph on X with edge lengths len(u, v). Note that d(p, cj ) ≥ d(p, ci ) = r ∗
since p ∈ Ci and C1 , . . . , Ck is an optimal clustering. Hence, for every (u, v): len(u, v) ≤ d(u, v)
and d′ (u, v) ≤ d(u, v). It is easy to see that
d′ (u, v) = min(d(u, v), d(u, p) + r ∗ + d(cj , v), d(v, p) + r ∗ + d(cj , u)).
Observe that since the ratio d(u, v)/len(u, v) is at most d(p, cj )/r ∗ ≤ α for all edges (u, v), we have
d(u, v)/d′ (u, v) ≤ α for all u and v. Hence, d(u, v) ≤ αd′ (u, v) ≤ αd(u, v), and consequently, d′ is
an (α, 1)-metric perturbation of d.
We now show that d′ is equal to d within the cluster Ci and within the cluster Cj .
Lemma 3.2. For all u, v ∈ Ci , we have d(u, v) = d′ (u, v), and for all u, v ∈ Cj , we have d(u, v) =
d′ (u, v).
Proof. I. Consider two points u, v in Ci . We need to show that d(u, v) = d′ (u, v). It suffices to
prove that
d(u, v) ≤ min(d(u, p) + r ∗ + d(cj , v), d(v, p) + r ∗ + d(cj , u)).

Assume without loss of generality that d(u, p) + r ∗ + d(cj , v) ≤ d(v, p) + r ∗ + d(cj , u). We have
d(u, p) + r ∗ + d(cj , v) = d(u, p) + d(p, ci ) + d(cj , v) ≥ d(u, ci ) + d(cj , v).
Since v ∈ Ci , we have d(v, ci ) ≤ d(v, cj ), and thus
d(u, p) + r ∗ + d(cj , v) ≥ d(u, ci ) + d(ci , v) ≥ d(u, v).

5

II. Consider two points u, v in Cj . Similarly to the previous case, we need to show that d(u, v) ≤
d(u, p) + r ∗ + d(cj , v). Since now u ∈ Cj , we have d(u, cj ) ≤ d(u, ci ). Thus,

d(u, p)+r ∗ +d(cj , v) = d(u, p)+d(p, ci ) +d(cj , v) ≥ d(u, ci )+d(cj , v) ≥ d(u, cj )+d(cj , v) ≥ d(u, v).

By the definition of α-metric perturbation stability, the optimal clusterings for metrics d and
d′ are the same. By Lemma 3.2, the distance functions d and d′ are equal within the clusters Ci
and Cj . Hence, the centers of Ci and Cj w.r.t. metric d′ are also points ci and cj , respectively (see
Definition 2.2, item 1). Thus, by the definition of center-based objective, d′ (ci , p) < d′ (cj , p), and,
consequently,
d(ci , p) = d′ (ci , p) < d′ (cj , p) = r ∗ = d(ci , p).
We get a contradiction, which finishes the proof.
Corollary 3.3. Consider a 2-metric perturbation resilient instance. Let C1 , . . . , Ck be an optimal
clustering with centers c1 , . . . , ck . Then each point u in Ci is closer to ci than to any point v outside
of Ci .
Proof. Suppose that v ∈ Cj for some j 6= i. By the triangle inequality, d(u, v) ≥ d(u, cj ) − d(cj , v).
By Lemma 3.1, d(u, cj ) > 2d(u, ci ) and d(cj , v) < d(ci , v)/2. Thus,
d(u, v) ≥ d(u, cj ) − d(cj , v) > 2d(u, ci ) −

d(ci , u) + d(u, v)
d(ci , v)
≥ 2d(u, ci ) −
.
2
2

In the last inequality, we used the triangle inequality d(ci , v) ≤ d(ci , u) + d(u, v). Rearranging the
terms, we get d(u, v) > d(ci , u).

4

Clustering Algorithm

In this section, we present our algorithm for solving 2-metric perturbation resilient instances of
clustering problems with natural center-based objectives. Our algorithm is based on single–linkage
clustering: first, we find a minimum spanning tree on the metric space X (e.g., using Kruskal’s
algorithm) and then run a dynamic programming algorithm on the spanning tree to find the clusters.
We describe the two steps of the algorithm in Sections 4.1 and 4.2.

4.1

Minimum Spanning Tree

At the first phase of the algorithm, we construct a minimum spanning tree on the points of the metric
space using Kruskal’s algorithm. Kruskal’s algorithm maintains a collection of trees. Initially, each
tree is a singleton point. At every step, the algorithm finds two points closest to each other that
belong to different trees and adds an edges between them. The algorithm terminates when all
points belong to the same tree. We denote the obtained spanning tree by T . The key observation
is that each cluster Ci forms a subtree of the spanning tree T .
Lemma 4.1. Each cluster Ci forms a subtree of the spanning tree T . In other words, the unique
path between every two vertices u, v ∈ Ci does not leave the cluster Ci .

6

Proof. Let ci be the center of Ci . We show that the (unique) path p from u to ci lies in Ci ,
and, therefore, the statement of Lemma 4.1 holds. Let u′ be the next vertex after u on the path p.
Consider the step at which Kruskal’s algorithm added the edge (u, u′ ). At that step, u and ci were in
distinct connected components (as p is the only path connecting u and ci ). Thus, d(u, u′ ) ≤ d(u, ci )
as otherwise the algorithm would have added the edge (u, ci ) instead of (u, u′ ). By Corollary 3.3,
the inequality d(u, u′ ) ≤ d(u, ci ) implies that u′ belongs to Ci . Proceeding by induction we conclude
that all vertices on the path p belong to Ci .

4.2

Dynamic Programming Algorithm

At the second phase, we use dynamic programming to compute the optimal clustering. We root
the tree T at an arbitrary vertex. We denote its root by root and the subtree rooted at u by Tu .
We first assume that the tree is binary. Later, we explain how to transform any tree into a binary
tree by adding dummy vertices.
The algorithm partitions the tree into (non-empty) subtrees P1 , . . . , Pk and assigns a center
ci ∈ Pi to all vertices in the subtree Pi so as to minimize the objective:
k
X

fci +

i=1

k X
X

gu (d(u, ci )).

(3)

i=1 u∈Pi

Lemma 4.1 implies that the optimal partitioning of X is the solution to this problem.
Let costu (k′ , c) be the minimum cost (3) of partitioning the subtree Tu into k′ subtrees P1 , . . . , Pk
and choosing k centers c1 , . . . , ck so that the following conditions hold:
1. u ∈ P1 and c1 = c (we denote the tree that contains u by P1 and require that its center be c).
2. if c1 ∈ Tu , then c1 ∈ P1 (if the center c1 of P1 lies in Tu , then it must be in P1 );
3. ci ∈ Pi for i > 1 (the center ci of every other tree Pi lies in Pi ).
That is, we assume that u belongs to the first subtree P1 and that c is the center for P1 . Every
center ci must belong to the corresponding set Pi except for c1 . However, if c1 ∈ Tu , then c1 ∈ P1 .
Denote the children of vertex u by lu and ru (recall that we assume that the tree is binary).
The cost costu (k′ , c) is computed using the following recursive formulas: if c ∈
/ Tlu ∪ Tru , then
costu (j, c) =fc + gu (d(c, u)) + min

(4)

′

′

′′

′

′

′′

′′

′

′′

′

′′

min{costlu (j , c ) + costru (j , c ) : j + j = j − 1, c ∈ Tlu , c ∈ Tru },
′′

′

(6)

′

′′

′′

(7)

min{costlu (j , c ) + costru (j , c) − fc : j + j = j, c ∈ Tlu },
′

′′

′′

(5)

′

min{costlu (j , c) + costru (j , c ) − fc : j + j = j, c ∈ Tru },

min{costlu (j ′ , c) + costru (j ′′ , c) − 2fc : j ′ + j ′′ = j + 1} .

(8)

If c ∈ Tlu , then we remove lines (5) and (6) from the formula. If c ∈ Tru , then we remove
lines (5) and (7) from the formula.
The first term fc + gu (d(c, u)) is the cost of opening a center in c and assigning u to c. The lines (5–
8) correspond to the following cases:
(5) neither lu nor ru is in P1 ; they are assigned to (trees Pi and Pj with centers) c′ and c′′ ,
(6) lu is not in P1 , but ru is in P1 ; they are assigned to c′ and c,
(7) lu is in P1 , but ru is not in P1 ; they are assigned to c and c′′ ,
7

(8) both lu and ru are in P1 ; they are assigned to c.
For leaves, we set costu (1, c) = fc + gu (d(u, c)) and costu (j, c) = ∞ for j > 1. Note that if we want
to find a partitioning of T into at most k subtrees, we can use a slightly simpler dynamic program.
It is easy to verify that the formulas above hold. The cost of the optimal partitioning of T into k
subtrees equals minc∈X costroot (k, c).
We now explain how to transform the tree T into a binary tree. If a vertex u has more than
two children, we add new dummy vertices between u and its children by repeating the following
procedure: take a vertex u having more than two children; pick any two children of u: u1 and u2 ;
create a new child v of u and rehang subtrees Tu1 and Tu2 to the vertex v. We forbid opening
centers in dummy vertices v by setting the opening cost fv to be infinity. We set the assignment
costs gv to be 0. Note that Lemma 4.1 still holds for the new tree if we place every dummy vertex
in the same part Pi as its parent.

5

Universal Separable Center-Based Clustering Objectives

In this section, we show that every separable center-based objective, satisfying some additional
properties, is a natural center-based objective. To this end, we define a universal center-based
objective and show that every universal center-based objective is a natural center-based objective.
Loosely speaking, a universal center-based objective is a center-based objective that satisfies
two properties, which we will discuss now:
• An arbitrary center-based objective is defined on a specific set of points X and can be used
to compute the cost of clustering only of the set X (given a metric d on X). In contrast, a
universal objective can be used to compute the cost of clustering of any ground
set X.
• Recall that in every optimal clustering with a center-based objective each point u ∈ X is
closer to the center of its own cluster than to the center of any other cluster. If a partition
is not optimal, some points might be closer to the centers of clusters that do not contain
them than to the centers of their own clusters. Then, we can move such points to other
clusters so as to minimize their distance to the cluster centers. In fact, one of the two
steps of Lloyd’s algorithm does exactly this; hence, we call such a transformation a Lloyd’s
improvement. We slightly strengthen the definition of a center-based objective by requiring
that a universal objective not increase when we make a Lloyd’s improvement of
any – not necessarily optimal – clustering.
Now we give a few auxiliary definitions and then formally define universal center-based objectives.
Since data sets used in applications are usually labeled, we will consider “labeled metric spaces”.
We will assume that the cost of clustering of X may depend on the distances between the points
in X and point labels (but not on the identities of points).
Definition 5.1 (Labeled Metric Space). A metric space labeled with a set of labels L is a pair
((X, d), l), where (X, d) is a metric space, and l : X → L is a function that assigns a label to each
point in X.
Definition 5.2 (Isomorphic Labeled Metric Spaces). We say that two metric spaces ((X ′ , d′ ), l′ )
and ((X ′′ , d′′ ), l′′ ) labeled with the same set L are isomorphic if there exists an isometry ϕ : X ′ → X ′′
(i.e., ϕ is a bijection that preserves distances: d′ (u, v) = d′′ (ϕ(u), ϕ(v)) for all u, v ∈ X ′ ) that
preserves labels; i.e. l′ (u) = l′′ (ϕ(u)) for all u ∈ X ′ .
8

We note that in the definition above the set L may be infinite. We denote the restriction of
((X, d), l) to a non-empty subset C ⊂ X by ((X, d), l)|C : ((X, d), l)|C = ((C, d|C ), l|C ). Note that
the restriction of a metric set labeled with L to a cluster C is also a metric set labeled with L.
Definition 5.3. Consider a clustering problem ((X, d), H, k) with a center-based objective. We say
that a clustering C1′ , . . . , Ck′ is a Lloyd’s improvement of a clustering C1 , . . . , Ck if there exists a set
of centers c1 , . . . , ck of C1 , . . . , Ck (i.e., each ci ∈ center(Ci , d)) such that
• ci ∈ Ci′ (a Lloyd’s improvement does not move the centers to other clusters)

• for every x ∈ X: if x ∈ Ci and x ∈ Cj′ , then d(x, cj ) ≤ d(x, ci ) (a Lloyd’s improvement may
move point x from Ci to Cj′ only if d(c, cj ) ≤ d(x, ci )).
Definition 5.4 (Universal Objective). We say that H is a universal center-based clustering objective for a label set L, if for every metric space ((X, d), l) labeled with L the problem ((X, d), Hl , k) is
a clustering problem with a separable center-based objective and the following two conditions hold.
1. Cluster scores Hl are universal (“can be used on any metric space”): Given any finite metric
space ((C, d), l) labeled with L, the function Hl (C, d) returns a real number – the cost of C;
and Hl′ (C ′ , d′ ) = Hl′′ (C ′′ , d′′ ) for any two isomorphic labeled metric spaces ((C ′ , d′ ), l′ ) and
((C ′′ , d′′ ), l′′ ).
2. If C1′ , . . . , Ck′ is a Lloyd’s improvement of C1 , . . . , Ck , then H(C1′ , . . . , Ck′ ; d) ≤ H(C1 , . . . , Ck ; d).
Note that every natural center-based objective is a universal objective. The label set is the set
of pairs (f, g), where f ∈ R is a real number; g is a nondecreasing function from R≥0 to R. Every
point x ∈ X is assigned the label l(x) = (fx , hx ). The score of a cluster C equals


X
gx (d(x, c)) ;
(9)
Hl (C, d) = min fc +
c∈C

x∈C


Hl (C, d) = min max fc , max gx (d(x, c) .
c∈C



x∈C

(10)

It is easy to see that Lloyd’s improvements may only decrease the cost of a clustering, since
the functions gx are non-decreasing. We now show that every clustering problem with universal
separable center-based objectives is a problem with natural center-based objectives.
Theorem 5.5. I. Let ((X, d), H, k) be a clustering problem with a universal center-based separable sum-objective. Then, the scoring function Hl can be represented as (9) for some nondecreasing functions fPand g such that the minimum is attained when c is a center of C; and thus
H(C1 , . . . , Ck ; d) = ki=1 Hl (Ci ; d|Ci ) is a natural center-based objective.
II. Let ((X, d), H, k) be a clustering problem with a universal center-based separable max-objective.
If the cost of any singleton cluster {x} equals 0, then the scoring function Hl can be represented as
(10) for some nondecreasing functions f and g such that the minimum is attained when c is a center
of C; ; and thus H(C1 , . . . , Ck ; d) = maxi∈{1,...,k} Hl (Ci ; d|Ci ) is a natural center-based objective.
Proof. I. For every label a ∈ L define two special labeled metric spaces Ma and Ma,a,r . The metric
space Ma is the metric space on a single point labeled with a; the metric space Ma,a,r is the metric
space on two points at distance r that are both labeled with a. Consider a point x ∈ X labeled
with a. Let fx = H(Ma ) and gx (r) = H(Ma,a,r ) − fx . We claim that the cost of any cluster C
equals
X

min fc +
gx (d(x, c)) ,
c∈C

x∈C\{c}

9

and the minimum is attained when c is a center of C. Consequently, equation (9) holds for functions
f˜c = fc − gc (0) and gx . To prove the claim, we construct a new metric space Cp′ for every p ∈ C.
The metric space Cp′ consists of all points of C and new points x′ , which are “duplicates” of points
x ∈ C \ {p}. We do not change distances between points in C and labels on the points from C.
We copy the label of each x to x′ ; i.e., we let l(x′ ) = l(x). We place x′ at the same location as the
point p. That is, we let d(x′ , y) = d(p, y) for all x, y ∈ C. Consider two clusterings of Cp′ . The first
clustering partitions Cp′ into the cluster C and singleton clusters {x′ } (there is a singleton cluster
for each x ∈ C \ {p}). The cost of each singleton cluster {x′ } equals fx , since {x′ } is isomorphic to
Ml(x) . Hence, the cost of the first clustering equals
X
Hl (C, d|C ) +
fx .
(11)
x∈C\{p}

The second clustering partitions C ′ into pairs of points {x, x′ } for each x ∈ C \{p} and the singleton
cluster {p}. The cost of each cluster {x, x′ } equals
H(Ma,a,d(x,x′ ) ) = gx (d(x, x′ )) + fx = gx (d(x, p)) + fx ,
since the cluster {x, x′ } is isomorphic to Ma,a,d(x,x′ ) . The cost of {p} equals fp . Hence, the cost of
the second clustering equals
X

fx + gx (d(x, c)) .
(12)
fp +
x∈C\{p}

x′

Note that the points x and
in each cluster {x, x′ } are symmetric, so we may assume that x′ is
the center of the cluster {x, x′ }. Observe that the first clustering is a Lloyd’s improvement of the
second clustering: To get the first clustering from the second clustering we move x from each cluster
{x, x′ } to the singleton cluster {p}. We are allowed to do that since d(x, p) = d(x, x′ ). Hence, the
cost of the second clustering is upper bounded by the cost of the first clustering. We have from (11)
and (12),
X
X
X

fx + gx (d(x, c)) −
fx = fp +
gx (d(x, c)).
(13)
Hl (C, d|C ) ≤ fp +
x∈C\{p}

x∈C\{p}

x∈C\{p}

On the other hand, if p is the center of C, then the second clustering is a Lloyd’s improvement of
the first one. Hence, (13) is an equality when p is the center of C.
It remains to show that functions gx are non-decreasing. We need to prove that for every
r1 ≥ r2 ≥ 0, gx (r1 ) ≥ gx (r2 ). We create a metric space on three points x′ , x′′ , x′′′ each having the
same label as x. Let d(x′ , x′′ ) = r1 , d(x′′ , x′′′ ) = r2 , d(x′ , x′′′ ) = r1 + r2 . The cost of clustering
{x′ , x′′ }, {x′′′ } equals 2fx + gx (r1 ); the cost of clustering {x′ }, {x′′ , x′′′ } equals 2fx + gx (r2 ). Since
r1 ≥ r2 , the second clustering is a Lloyd’s improvement of the first one. Hence, 2fx + gx (r2 ) ≤
2fx + gx (r1 ) and gx (r2 ) ≤ gx (r1 ). This completes the proof of part I. The proof of part II is
similar.

References
[1] Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation
stability. Information Processing Letters, 112(1):49–54, 2012.
[2] Maria-Florina Balcan, Nika Haghtalab, and Colin White. Symmetric and asymmetric k-center
clustering under stability. In Proceedings of the International Colloquium on Automata, Languages, and Programming, 2016.
10

[3] Maria-Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. SIAM Journal on Computing, 2016.
[4] Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks. On the practically interesting
instances of maxcut. In Proceedings of the Symposium on Theoretical Aspects of Computer
Science, pages 526–537, 2013.
[5] Yonatan Bilu and Nathan Linial. Are stable instances easy?
Science, pages 332–341, 2010.

In Innovations in Computer

[6] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Bilu—Linial stable
instances of Max Cut and Minimum Multiway Cut. In Proceedings of the Symposium on Discrete
Algorithms, pages 890–906, 2014.
[7] Matúš Mihalák, Marcel Schöngens, Rastislav Šrámek, and Peter Widmayer. On the complexity
of the metric tsp under stability considerations. In SOFSEM 2011: Theory and Practice of
Computer Science, pages 382–393. Springer, 2011.

11

