Maximum gradient embeddings and monotone clustering

Manor Mendel Computer Science Division The Open University of Israel

                 mendelma@gmail.com

Assaf Naor Courant Institute New York University

                                           naor@cims.nyu.edu

Abstract

Let (X, d_{X}) be an n-point metric space. We show that there exists a distribution 𝒟 over non-contractive embeddings into trees f : X → T such that for every x ∈ X,

𝒟 [ max_{y∈X\\{x\}}\frac{d_{T}(f (x), f (y))}{d_{X}(x, y)}] C(logn)^{2},

where C is a universal constant. Conversely we show that the above quadratic dependence on logn cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location.

1 Introduction

Metric embeddings are an invaluable tool in analysis, Riemannian geometry, group theory, graph theory, and the design of approximation algorithms. In most cases embeddings are used to “simplify” a geometric object that we wish to understand, or on which we need to perform certain algorithmic tasks. Thus one tries to faithfully represent a metric space as a subset of another space with controlled geometry, whose structure is well enough understood to successfully address the problem at hand. There is some obvious flexibility in this approach: Both the choice of target space and the notion of faithfulness of an embedding can be adapted to the problem that we wish to solve. Of course, once these choices are made, the main difficulty is the construction of the required embedding, and in the algorithmic context we have the additional requirement that the embedding can be computed efficiently.

In this paper we introduce a new notion of embedding, called maximum gradient embeddings, which turns out to be perfectly suited for approximating a wide range of clustering problems. We then provide optimal maximum gradient embeddings of general finite metric spaces, and use them to design approximation algorithms for several clustering problems. These embeddings yield a generic approach to many problems, and we give some examples that illustrate this fact.

Due to their special structure, it is natural to try to embed metric spaces into trees. This is especially important for algorithmic purposes, as many hard problems are tractable on trees. Unfortunately, this is too much to hope for in the bi-Lipschitz category: As shown by Rabinovich and Raz [35] the n-cycle incurs distortion Ω(n) in any embedding into a tree. However, one can relax this idea and look for a random embedding into a tree which is faithful on average.

Randomized embeddings into trees via mappings which do not contract distances (also known as probabilistic embeddings into dominating trees) became an important algorithmic paradigm due to the work of Bartal [3, 4] (see also [1, 16] for the related problem of embedding graphs into distributions over spanning trees). This work led to the design of many approximation algorithms for a wide range of NP hard problems. In some cases the best known approximation factors are due to the “probabilistic tree” approach, while in other cases improved algorithms have been subsequently found after the original application of probabilistic embeddings was discovered. But, in both cases it is clear that the strength of Bartal’s approach is that it is generic: For a certain type of problem one can quickly get a polylogarithmic approximation using probabilistic embedding into trees, and then proceed to analyze certain particular cases if one desires to find better approximation guarantees. However, probabilistic embeddings into trees do not always work. In [7] Bartal and Mendel introduced the weaker notion of multi-embeddings, and used it to design improved algorithms for special classes of metric spaces. Here we strengthen this notion to maximum gradient embeddings, yielding a faithfulness measure which is nevertheless weaker than bi-Lipschitz, and use it to design approximation algorithms for harder problems to which regular probabilistic embeddings do not apply.

Let (X, d_{X}) and (Y, d_{Y}) be metric spaces, and fix a mapping f : X → Y. We shall say that f is noncontractive if for every x, y ∈ X we have d_{Y}(f (x), f (y)) d_{X}(x, y). The maximum gradient of f at a point x ∈ X is defined as

|∇f (x)|_{∞} = sup_{y∈X\\{x\}}\frac{d_{Y}(f (x), f (y))}{d_{X}(x, y)}.  (1)

Thus the Lipschitz constant of f is given by

∥f ∥_{Lip} = sup_{x∈X}|∇f (x)|_{∞} .

Note that in the mathematical literature, mostly in the context of the study of isoperimetry on general geodesic metric measure spaces (see for example [8,28]), it is common to define the modulus of the gradient of f at x ∈ X as

|∇f (x)| = lim sup_{y→x} \frac{d_{Y}(f (x), f (y))}{d_{X}(x, y)}.  (2)

The definition in (2) is very natural in the context of connected metric spaces, but in the context of finite metric spaces it clearly makes more sense to deal with the maximum gradient as defined in (1).

In what follows when we refer to a tree metric we mean the shortest-path metric on a graph-theoretical tree with weighted edges. Recall that (U, d_{U}) is an ultrametric if for every u, v, w ∈ U we have d_{U}(u, v) max{d_{U}(u, w), d_{U}(w, v)}. It is well known that ultrametrics are tree metrics. The following result is due to Fakcharoenphol, Rao and Talwar [17], and is a slight improvement over an earlier theorem of Bartal [4]. For every n-point metric space (X, d_{X}) there is a distribution 𝒟 over non-contractive embeddings into ultrametrics f : X → U such that

max_{\begin{matrix}x,y∈X \\ x y \end{matrix}} _{𝒟} [\frac{d_{U}(f (x), f (y)}{d_{X}(x, y)}] = O(logn).  (3)

The logarithmic upper bound in (3) cannot be improved in general.

Inequality (3) is extremely useful for optimization problems whose objective function is linear in the distances, since by linearity of expectation it reduces such tasks to trees, with only a logarithmic loss in the approximation guarantee. When it comes to non-linear problems, the use of (3) is very limited. We will show that this issue can be addressed using the following theorem, which is our main result.

Theorem 1. Let (X, d_{X}) be an n-point metric space. Then there exists a distribution 𝒟 over non-contractive embeddings into ultrametrics f : X → U (thus both the ultrametric (U, d_{U}) and the mapping f are random) such that for every x ∈ X,

𝒟 [|∇f (x)|_{∞} ] C(logn)^{2},

where C is a universal constant.

On the other hand there exists a universal constant c > 0 and arbitrarily large n-point metric spaces Y_{n} such that for any distribution over non-contractive embeddings into trees f : Y_{n} → T there is necessarily some x ∈ Y_{n} for which

𝒟 [|∇f (x)|_{∞} ] c(logn)^{2}.

We call embeddings as in Theorem 1, i.e. embeddings with small expected maximum gradient, maximum gradient embeddings into distributions over trees (in what follows we will only deal with distributions over trees, so we will drop the last part of this title when referring to the embedding, without creating any ambiguity). The proof of the upper bound in Theorem 1 is a modification of an argument of Fakcharoenphol, Rao and Talwar [17], which is based on ideas from [3, 11]. It uses the same stochastic decomposition of metric spaces as in [17], but it relies on properties of it which are well known to experts, yet have not been exploited in full strength in previous applications. The argument appears in Section 2. Alternative proofs of the main technical step of the proof of the upper bound in Theorem 1 can be also deduced from the results of [32] or an argument in the proof of Lemma 2.1 in [20]. In both of these references the required inequality is deduced from an improved analysis of the specific stochastic decomposition of Calinescu, Karloff and Rabani [11] that was used in [17]. Here we present a different approach, which shows that the “padding inequality” proved by Fakcharoenphol, Rao and Talwar in [17] can be used as a “black box” to yield a maximum gradient embedding, and there is no need to recall how the stochastic decomposition was originally defined.

The heart of this paper is the lower bound in Theorem 1. The metrics Y_{n} in Theorem 1 are the diamond graphs of Newman and Rabinovich [34], which will be defined in Section 3. These graphs have been previously used as counter-examples in several embedding problems— see [10, 21, 29, 34]. In particular, we were inspired to consider these examples by the proof in [21] of the fact that they require distortion Ω(logn) in any probabilistic embedding into trees. However, our proof of the Ω((logn)^{2}) lower bound in Theorem 1 is considerably more delicate than the proof in [21]. This proof, together with other lower bounds for maximum gradient embeddings, is presented in Section 3.

1.1 A framework for clustering problems with monotone costs

We now turn to some algorithmic applications of Theorem 1. The general reduction in Theorem 2 below should also be viewed as an explanation why maximum gradient embeddings are so natural— they are precisely the notion of embedding which allows such reductions to go through.

A general setting of the clustering problem is as follows. Let X be an n-point set, and denote by MET(X) the set of all metrics on X. A possible clustering solution consists of sets of the form {(x_{1}, C_{1}), …, (x_{k}, C_{k})} where x_{1}, …, x_{k} ∈ X and C_{1}, …, C_{k} ⊆ X. We think of C_{1}, …, C_{k} as the clusters, and x_{i} as the “center” of C_{i}. In this general framework we do not require that the clusters cover X, or that they are pairwise disjoint, or that they contain their centers. Thus the space of possible clustering solution is S 2^{X×2^{X}} (though the exact structure of S does not play a role in the proof of Theorem 2 below). Assume that for every point x ∈ X, every metric d ∈ MET(X), and every possible clustering solution P ∈ S, we are given Γ(x, d, P) ∈ [0, ∞], which we think of as a measure of the dissatisfaction of x with respect to P and d. Our goal is to minimize the average dissatisfaction of the points of X. Formally, given a measure of dissatisfaction (which we also call in what follows a clustering cost function) Γ : X × MET(X) × S → [0, ∞], we wish to compute for a given metric d ∈ MET(X) the value

Opt_{Γ}(X, d) =^{def} min {∑_{x∈X}Γ(x, d, P) : P ∈ S}

(Since we are mainly concerned with the algorithmic aspect of this problem, we assume from now on that Γ can be computed efficiently.)

We make two natural assumptions on the cost function Γ. First of all, we will assume that it scales homogeneously with respect to the metric, i.e. for every λ > 0, x ∈ X, d ∈ MET(X) and P ∈ S we have Γ(x, λd, P) = λΓ(x, d, P). Secondly we will assume that Γ is monotone with respecting to the metric, i.e. if d, \overline{d} ∈ MET(X) and x ∈ X satisfy d(x, y) \overline{d}(x, y) for every y ∈ X then Γ(x, d, P) Γ(x, \overline{d}, P). In other words, if all the points in X are further with respect to \overline{d} from x then they are with respect to d, then x is more dissatisfied. This is a very natural assumption to make, as most clustering problems look for clusters which are small in various (metric) senses. We call clustering problems with Γ satisfying these assumptions monotone clustering problems. Essentially all the algorithmic minimization problems that have benefitted from an application of (3) can be cast as monotone clustering problems, but this framework also applies to some “non-linear” clustering optimization problems, as we shall see presently.

The following theorem is a simple application of Theorem 1. It shows that it is enough to solve monotone clustering problems on ultrametrics, with only a polylogarithmic loss in the approximation factor.

Theorem 2 (reduction to ultrametrics). Let X be an n-point set and fix a homogeneous monotone clustering cost function Γ : X × MET(X) × S → [0, ∞]. Assume that there is a randomized polynomial time algorithm which approximates Opt_{Γ}(X, ρ) to within a factor α(n) on any ultrametric ρ ∈ MET(X). Then there is a randomized polynomial time algorithm which approximates Opt_{Γ}(X, d) on any metric d ∈ MET(X) to within a factor of O (α(n)(logn)^{2}).

Proof. Let (X, d) be an n-point metric space and let 𝒟 be the distribution over random ultrametrics ρ on X from Theorem 1 (which is computable in polynomial time, as follows directly from our proof of Theorem 1 in Section 2). In other words, ρ(x, y) d(x, y) for all x, y ∈ X and

max_{x∈X} _{𝒟} [ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d(x, y)}] C(logn)^{2}.

Let P ∈ S be a clustering solution for which

Opt_{Γ}(X, d) = ∑_{x∈X}Γ(x, d, P).

Using the monotonicity and homogeneity of Γ we see that

Opt_{Γ}(X, ρ)  ∑_{x∈X}Γ(x, ρ, P) ∑_{x∈X}Γ (x, [ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d(x, y)}]· d, P)= ∑_{x∈X}[ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d(x, y)}]· Γ(x, d, P).

Taking expectation we conclude that

𝒟 [Opt_{Γ}(X, ρ)] ∑_{x∈X}( _{𝒟} [ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d(x, y)}]) Γ(x, d, P) C(logn)^{2} · Opt_{Γ}(X, d).

Hence, with probability at least \frac{1}{2} we have

Opt_{Γ}(X, ρ) 2C(logn)^{2} · Opt_{Γ}(X, d).

For such ρ compute a clustering solution Q ∈ S satisfying

∑_{x∈X}Γ(x, ρ, Q) α(n)Opt_{Γ}(X, ρ) 2Cα(n)(logn)^{2} · Opt_{Γ}(X, d).

Since ρ d it remains to use the monotonicity of Γ once more to deduce that

∑_{x∈X}Γ(x, ρ, Q) ∑_{x∈X}Γ(x, d, Q) Opt_{Γ}(X, d).

Thus Q is a O (α(n)(logn)^{2})approximate solution to the clustering problem on (X, d) with cost Γ.

Theorem 2 is a generic reduction, and in many particular cases it might be possible use a case-specific analysis to improve the O ((logn)^{2}) loss in the approximation factor. However, as a general reduction paradigm for clustering problems, Theorem 2makes it clear why maximum gradient embeddings are natural.

We shall now demonstrate the applicability of the monotone clustering framework to two concrete examples called fault-tolerant k-median clustering and Σℓ_{p} clustering. We are not aware of a previous investigation of these problems, but we believe that they are quite natural. It also seems plausible that, just as in the problems for which Bartal’s method originally yielded the first non-trivial algorithmic results, a better approximation factor might be obtainable via more problem-specific tools.

Fault-tolerant k-median and facility location. The k-median problem is as follows. Given an n-point metric space (X, d_{X}) and k ∈ , find x_{1}, …, x_{k} ∈ X that minimize the objective function

∑_{x∈X} min_{j∈{x_{1},...,x_{k}}}d_{X}(x, x_{j}).  (4)

This very natural and well studied problem can be easily cast as monotone clustering problem by defining Γ(x, d, {(x_{1}, C_{1}), …, (x_{m}, C_{m})}) to be ∞ if m k, and otherwise

Γ(x, d, {(x_{1}, C_{1}), …, (x_{m}, C_{m})}) = min_{j∈{x_{1},...,x_{k}}}d(x, x_{j}).

The linear structure of (4) makes it a prime example of a problem which can be approximated using Bartal’s probabilistic embeddings. Indeed, the first non-trivial approximation algorithm for k-median clustering was obtained by Bartal in [4] (another such example is Min-Sum clustering— see [5]). Since then this problem has been investigated extensively: The first constant factor approximation for it was obtained in [13] using LP rounding, and the first combinatorial (primal-dual) constant-factor algorithm was obtained in [24]. In [2] an analysis of a natural local search heuristic yields the best known approximation factor for k-median clustering.

Here we study the following fault-tolerant version of the k-median problem. Let (X, d) be an n-point metric space and fix k ∈ . Assume that for every x ∈ X we are given an integer j(x) ∈ X (which we call the fault-tolerant parameter of x). Given x_{1}, …, x_{k} and x ∈ X let x_{j}^{∗}(x; d) be the j-th closest point to x in {x_{1}, …, x_{k}}. In other words, {x_{j}^{∗}(x; d)}_{j=1}^{k} is a re-ordering of {x_{j}}_{j=1}^{k} such that d(x, x_{1}^{∗}(x; d)) ⋯ d(x, x_{k}^{∗}(x; d)). Our goal is to minimize the objective function

∑_{x∈X}d (x, x_{j(x)}^{∗}(x; d)).  (5)

To understand (5) assume for the sake of simplicity that j(x) = j for all x ∈ X. If {x_{j}}_{j=1}^{k} minimize (5) and j − 1 of them are deleted (due to possible noise), then we are still ensured that on average every point in X is close to one of the x_{j}. In this sense the clustering problem in (5) is fault-tolerant. In other words, the optimum solution of (5) is insensitive to (controlled) noise. Observe that for j = 1 we return to the k-median clustering problem.

We remark that another fault-tolerant version of k-median clustering was introduced in [25]. In this problem we connect each point x in the metric space X to j(x) centers, but the objective function is the sum over x ∈ X of the sum of the distances from x to all the j(x) centers. Once again, the linearity of the objective function seems to make the problem easier, and in [37] a constant factor approximation is achieved (this immediately implies that our version of fault-tolerant k-median clustering, i.e. the minimization of (5), has a O (max_{x∈X}j(x)) approximation algorithm). In particular, the LP that was previously used for k-median clustering naturally generalizes to this setting. This is not the case for our fault-tolerant version in (5). Moreover, the local search techniques for k-median clustering (see for example [2]) do not seem to be easily generalizable to the case j > 1, and in any case seem to require n^{Ω(j)} time, which is not polynomial even for moderate values of j.

Arguing as above in the case of k-median clustering we see that the fault-tolerant k-median clustering problem in (5) is a monotone clustering problem. In Section 4.1 we show that it can be solved exactly in polynomial time on ultrametrics. Thus, in combination with Theorem 2, we obtain a O ((logn)^{2}) approximation algorithm for the minimization of (5) on general metrics.

Remark 1. Facility location type problems have been studied extensively since the 1960’s— we refer to the book [33], and specifically to the chapter on uncapacitated facility location [15], for a discussion of such problems. The uncapacitated metric facility location problem is closely related to k-median problem (indeed k-median can be reduced to it via Lagrangian relaxation— see [24]), and has been studied extensively in recent years (see [12, 19, 23, 24, 26, 36]). In the context of (5) we can also consider the following faulttolerant version of the facility location problem. Assume in addition that we are given non-negative facility costs {f_{x}}_{x∈X}. Then the goal is to minimize over all x_{1}, …, x_{k} ∈ X the objective function

∑_{j=1}^{k} f_{x_{j}} + ∑_{x∈X}d (x, x_{j(x)}^{∗}(x; d)).  (6)

The case j(x) ≡ 1 reduces to the classical un-capacitated metric facility location problem. The techniques presented here can be easily generalized to yield a O ((logn)^{2})approximation algorithm for the minimization of (6) as well.

Σℓ_{p} clustering. Another problem which illustrates the usefulness of Theorem 2is the Σℓ_{p} clustering problem which we now describe. Our argument for this problem is quite general, and it applies to more cost functions, but it is beneficial to concentrate on a concrete example. For p ∈ [1, ∞] the Σℓ_{p} clustering problem is as follows: For a metric space (X, d) and k ∈ the goal is to find x_{1}, …, x_{k} ∈ X and a partition of X into k sets C_{1}, …, C_{k} ⊆ X which minimize the objective function

∑_{j=1}^{k} (∑_{x∈C_{j}} d(x, x_{j})^{p})^{1/p}.  (7)

When p = 1 this becomes the k-median problem, and when p = ∞ this is the “sum of the cluster radii” problem, which has been studied in [14]. In both of these extreme cases there is a constant factor approximation algorithm known, so we automatically get a O (min{n^{1/p}, n^{1−1/p}})approximation algorithm for (7). Here we shall use the framework of Theorem 2 to give a O ((logn)^{2}) approximation algorithm for this problem for general p.

Observe that the Σℓ_{p} clustering problems are monotone clustering problems. Indeed, all we need to do is define Γ(x, d, {(x_{1}, C_{1}), …, (x_{m}, C_{m})}) to be ∞ if {C_{1}, …, C_{m}} is not a partition of X or m k. Otherwise set Γ(x, d, {(x_{1}, C_{1}), …, (x_{k}, C_{k})}) = 0 if x {x_{1}, …, x_{k}} and for j ∈ {1, …, k},

Γ(x_{j}, d, {(x_{1}, C_{1}), …, (x_{k}, C_{k})}) = (∑_{x∈C_{j}} d(x, x_{j})^{p})^{1/p}.

This definition clearly makes Γ a homogeneous monotone clustering cost function for any p ∈ [1, ∞]. The following lemma, combined with Theorem 2, therefore implies that the Σℓ_{p} clustering problem has a O ((logn)^{2})approximation algorithm.

Lemma 3. The Σℓ_{p} clustering problem has a constant factor polynomial time approximation algorithm (even a FPTAS) on ultrametrics.

Lemma 3 will be proved via dynamic programming in Section 4.1.

2 Proof of the upper bound in Theorem 1

We start by recalling some terminology and results concerning random partitions of metric spaces. Given a partition 𝒫 of a finite metric space (X, d_{X}) and x ∈ X we denote by 𝒫(x) the unique element of 𝒫 to which x belongs. For Δ > 0 the partition 𝒫 is said to be Δ-bounded if for every x ∈ X we have diam(𝒫(x)) Δ. We also fix a positive measure μ on X. The following fundamental result is due to [17] when μ is the uniform measure on X. The case of general measures was observed in [27, 30], and the specific numerical constants used below are taken from [32].

Lemma 4. For every Δ > 0 there exists a distribution over Δ-bounded partitions 𝒫 of X such that for every x ∈ X and every 0 < t Δ/8,

Pr[B_{X}(x, t) 𝒫(x)] \frac{16t}{Δ} · log \frac{μ(B_{X}(x, Δ))}{μ(B_{X}(x, Δ/8))}.  (8)

We also recall the notion of a quotient of a metric space (see [9, 18, 31]). Let 𝒲 = {W_{1}, …, W_{m}} be a partition of X. For W, W′ ∈ 𝒲 write d_{X}(W, W′) = min{d_{X}(x, y) : x ∈ W, y ∈ W′}. The quotient metric space (X/𝒲 , d_{X/𝒲} ) is define as follows. As a set X/𝒲 coincides with 𝒲 . The metric d_{X/𝒲} is the maximal metric on 𝒲 which is majorized by d_{X}(·, ·). In other words, for W, W′ ∈ 𝒲 ,

d_{X/𝒲} (W, W′) = min {∑_{j=1}^{m−1}d_{X}(V_{j−1} , V_{j}) : V_{0}, …, V_{m−1} ∈ 𝒲 , V_{0} = W, V_{m−1} = W′} .

Note that the V_{j}’s in the definition above need not be distinct.

The following lemma is a well known “quotient version” of Lemma 4. The argument dates back at least to Bartal [3], and appeared in various guises in several other places— see for example [22, 32]. Since we couldn’t locate the formulation that we need in the literature, we include a proof here.

Lemma 5. Let (X, d_{X}) be an n-point metric space and Δ > 0. Then there exists a distribution over Δbounded partitions 𝒫 of X such that for every x, y ∈ X, if d_{X}(x, y) \frac{Δ}{2n} then 𝒫(x) = 𝒫(y), and for every x ∈ X and 0 < t Δ/16,

Pr[B_{X}(x, t) 𝒫(x)] \frac{32t}{Δ} · log \frac{μ(B_{X}(x, Δ))}{μ(B_{X}(x, Δ/16))}.

Proof. Define an equivalence relation on X by x ∼ y if there exists k ∈ N and x_{0}, …, x_{k} ∈ X such that x_{0} = x, x_{k} = y and d_{X}(x_{i−1}, x_{i}) \frac{δ}{2n} for all i ∈ \{1, …, k\}. Let 𝒲 = \{W_{1}, …, W_{m}\} be the equivalence classes of this relation, and consider the quotient metric space X/𝒲 . We also denote by π : X → 𝒲 the induced quotient map, i.e. for x ∈ W_{j}, π(x) = W_{j}. Let μ ∘ π^{−1} be the measure on 𝒲 given for W ∈ 𝒲 by μ ∘ π^{−1}(W) = μ(π^{−1}(W)). Observe that for every x, y ∈ X,

d_{X}(x, y) − \frac{Δ}{2} d_{X/𝒲} (π(x), π(y)) d_{X}(x, y).  (9)

Indeed, the upper bound in (9) is immediate from the definition of a quotient metric. The lower bound in (9) is proved as follows. There are points x = x_{0}, x_{1}, …, x_{m−1} = y in X such that the sets {π(x_{j})}_{j=0}^{m−1} are distinct (and hence disjoint), and d_{X/𝒲} (π(x), π(y)) = ∑ _{j=1}^{m−1} d_{X}(π(x_{j−1} ), π(x_{j})). For j ∈ {1, …, m − 1} let a_{j} ∈ π(x_{j−1} ) and b_{j} ∈ π(x_{j}) be such that d_{X}(a_{j}, b_{j}) = d_{X}(π(x_{j−1} ), π(x_{j})). Since, by the definition of the equivalence relation ∼, for all z ∈ X we have diam(π(z)) = max_{a,b∈π(z)}d_{X}(a, b) \frac{(|π(z)|−1)Δ}{2n} we get that

d_{X}(x, y) d_{X}(x, a_{1}) + ∑_{j=1}^{m−1}d_{X}(a_{j}, b_{j}) + ∑_{j=1}^{m−2}d_{X}(b_{j}, a_{j+1} ) + d_{X}(b_{m−1}, y)

∑_{j=0}^{m−1} \frac{(|π(x_{j})| − 1)Δ}{2n} + d_{X/𝒲} (π(x), π(y)) \frac{Δ}{2} + d_{X/𝒲} (π(x), π(y)),

implying the lower bound in (9).

Let 𝒬 be a distribution over Δ/2-bounded partitions of X/𝒲 such that for every W ∈ 𝒲 and every 0 < t Δ/16 we have

Pr[B_{X/𝒲} (W, t) 𝒬(W)] \frac{32t}{Δ} · log \frac{μ ∘ π^{−1}(B_{X/𝒲} (W, Δ/2))}{μ ∘ π^{−1}(B_{X/𝒲} (W, Δ/16))}.  (10)

The existence of 𝒬 follows from Lemma 4. Let 𝒫 be the partition of X given by 𝒫 = {π^{−1}(A) : A ∈ 𝒬}. Note that (9) implies that for every x ∈ X we have π^{−1} (B_{X/𝒲} (π(x), Δ/2)) ⊆ B_{X}(x, Δ) and for every t > 0, π^{−1} (B_{X/𝒲} (π(x), t))⊇ B_{X}(x, t). Thus (10) implies that for every x ∈ X and 0 < t Δ/16,

Pr[B_{X}(x, t) 𝒫(x)] Pr[B_{X/𝒲} (π(x), t) 𝒬(π(x))] \frac{32t}{Δ} · log \frac{μ(B_{X}(x, Δ))}{μ(B_{X}(x, Δ/16))}.

It remains to note that (9) implies that 𝒫 is Δ-bounded and if d_{X}(x, y) \frac{Δ}{2n} then x ∼ y, which means that π(x) = π(y), so that 𝒫(x) = 𝒫(y).

Proof of the upper bound in Theorem 1. For every k ∈ let 𝒫_{k} be a random partition sampled from the distribution over partitions of X from Lemma 5 with Δ = 16^{k}, where μ is the counting measure on X (we assume in what follows that the distributions for different values of k are independent). For x, y ∈ X let k be the largest integer for which 𝒫_{k}(x) 𝒫_{k}(y) (such a k must exists since for small enough k we have 𝒫_{k}(z) = {z} for all z ∈ X). Denote ρ(x, y) = 16^{k+1}. Then ρ is a (random) ultrametric on X. Indeed, if x, y, z ∈ X and ρ(x, y) = 16^{k+1} then 𝒫_{k}(x) 𝒫_{k}(y). It follows that either 𝒫_{k}(z) 𝒫_{k}(x) or 𝒫_{k}(z) 𝒫_{k}(y). Thus by the definition of ρ we have that max{ρ(x, z), ρ(y, z)} ρ(x, y). Note also that if ρ(x, y) = 16^{k+1} then 𝒫_{k+1}(x) = 𝒫_{k+1}(y), so that d_{X}(x, y) diam(𝒫(x)) 16^{k+1} = ρ(x, y). It follows that the identity mapping on X is a random non-contractive embedding of X into the ultrametric (X, ρ). Finally, since whenever d_{X}(x, y) \frac{16^{k}}{2n} we have 𝒫_{k}(x) = 𝒫_{k}(y), we are ensured that ρ(x, y) 32nd_{X}(x, y) for every x, y ∈ X.

Denote for x ∈ X and i ∈ , A_{i}(x) = B_{X}(x, 16^{i})\B_{X}(x, 16^{i−1}). For every j ∈ and k ∈ if B_{X}(x, 16^{k−j}) ⊆ 𝒫_{k}(x) then for every y ∈ B_{X}(x, 16^{k−j}) we have 𝒫_{k}(x) = 𝒫_{k}(y), and therefore by the definition of ρ(x, y) we have ρ(x, y) 16^{k}. Thus, if y ∈ A_{k−j}(x) we have ρ(x, y) 16^{k} < 16^{j+1} d_{X}(x, y). This establishes the following inclusion of events:

\{ max_{y∈A_{k−j}(x)} \frac{ρ(x, y)}{d_{X}(x, y)} 16^{j+1} \} ⊆ \{B_{X}(x, 16^{k−j}) 𝒫_{k}(x)\} .

hence

Pr[ max_{y∈A_{k−j}(x)} \frac{ρ(x, y)}{d_{X}(x, y)} 16^{j+1} ] Pr[B_{X}(x, 16^{k−j}) 𝒫_{k}(x)] \frac{32}{16^{j}} · log \frac{|B_{X}(x, 16^{k})|}{|B_{X}(x, 16^{k−1})|}.

Thus, since X = ⋃ _{i∈} A_{i}(x), we see that

Pr[ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d_{X}(x, y)} 16^{j}] = Pr [⋃_{i∈} \{ max_{y∈A_{i}(x)} \frac{ρ(x, y)}{d_{X}(x, y)} 16^{j}\} ] ∑_{i∈} Pr[ max_{y∈A_{i}(x)} \frac{ρ(x, y)}{d_{X}(x, y)} 16^{j}]

∑_{i∈} \frac{32}{16^{j−1}} · log \frac{|B_{X}(x, 16^{i+j−1} )|}{|B_{X}(x, 16^{i+j−2} )|} \frac{512}{16^{j}} · logn. (11)

It follows that there exists a universal constant C > 0 such that for all u > 0 we have

Pr[ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d_{X}(x, y)} u] \frac{C logn}{u}.

Hence, using the a priori bound ρ(x, y) 32nd_{X}(x, y), it follows that

[ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d_{X}(x, y)}] = ∫ _{0}^{32n}Pr[ max_{y∈X\\{x\}}\frac{ρ(x, y)}{d_{X}(x, y)} u] du ∫ _{0}^{32n}min\{1, \frac{C logn}{u}\} du = O (1 + (logn)^{2}) .

This completes the proof of the upper bound in Theorem 1.

Remark 2. The above argument also shows that for every n-point metric space (X, d_{X}) there exists a distribution over non-contractive embeddings into ultrametrics f : X → U such that

𝒟 [|∇f (x)|_{∞} ] = O (1 + (logn) logΦ(X)) ,

where Φ(X) is the aspect ratio of X, which is defined by

Φ(X) = \frac{diamX}{min\begin{matrix}x,y∈X \\ x y \end{matrix}d_{X}(x, y)}= \frac{max_{x,y∈X}d_{X}(x, y)}{min\begin{matrix}x,y∈X \\ x y \end{matrix}d_{X}(x, y)}.

3 Tight lower bounds for cycles, paths, and diamond graphs

As mentioned in the introduction, the metrics Y_{n} in Theorem 1 are the diamond graphs of Newman and Rabinovich [34], which will be defined presently. Before passing to this more complicated (and strongest) lower bound, we will analyze the simpler examples of cycles and paths, which are of independent interest.

Let C_{n}, n > 3, be the unweighted path on n-vertices. We will identify C_{n} with the group _{n} of integers modulo n. We first observe that in this special case the upper bound in Theorem 1 can be improved to O(logn). This is achieved by using Karp’s embedding of the cycle into spanning paths— we simply choose an edge of C_{n} uniformly at random and delete it. Let f : C_{n} → be the randomized embedding thus obtained, which is clearly non-contractive.

As Karp observed, one can readily verify that as a probabilistic embedding into trees f has distortion at most 2. We will now show that as a maximum gradient embedding, f has distortion Θ(logn). Indeed, fix x ∈ C_{n}, and denote the deleted edge by {a, a + 1}. Assume that d_{C_{n}}(x, a) = t n/2 − 1. Then the distance from a + 1 to x changed from t + 1 in C_{n} to n − t − 1 in the path. It is also easy to see that this is where the maximum gradient is attained. Thus

[|∇f (x)|_{∞} ] ≈ \frac{2}{n} ∑_{0 t n/2} \frac{n − t − 1}{t + 1} = Θ(logn).

We will now show that any maximum gradient embedding of C_{n} into a distribution over trees incurs distortion Ω(logn). For this purpose we will use the following lemma from [35].

Lemma 6. For any tree metric T, and any non-contractive embedding g : C_{n} → T, there exists an edge (x, x + 1) of C_{n} such that d_{T}(g(x), g(x + 1)) \frac{n}{3} − 1.

Now, let 𝒟 be a distribution over non-contractive embeddings of C_{n} into trees f : C_{n} → T. By Lemma 6 we know that there exists x ∈ C_{n} such that d_{T}(f (x), f (x + 1)) \frac{n−3}{3}. Thus for every y ∈ C_{n} we have that max\{d_{T}(f (y), f (x)), d_{T}(f (y), f (x+1))\} \frac{n−3}{6}. On the other hand max\{d_{C_{n}}(y, x), d_{C_{n}}(y, x+1)\} d_{C_{n}}(x, y)+1. It follows that

|∇f (y)|_{∞} \frac{n − 3}{6d_{C_{n}}(x, y) + 6}.

Summing this inequality over y ∈ C_{n} we see that

∑_{y∈C_{n}}|∇f (y)|_{∞} ∑_{0 k n/2} \frac{n − 3}{6k + 6} = Ω(n logn).

Thus

max_{y∈C_{n}} _{𝒟} [|∇f (y)|_{∞} ] \frac{1}{n} ∑_{y∈C_{n}} _{𝒟} |∇f (y)|_{∞} = Ω(logn),

as required.

We will now deal with the more complicated case of maximum gradient embeddings of the unweighted path on n-vertices, which we denote by P_{n}, into ultrametrics. The following proposition shows that Theorem 1 is optimal when one considers embeddings into ultrametrics. This is weaker than the lower bound in Theorem 1, which deals with embeddings into arbitrary trees (note that P_{n} is a tree).

Proposition 7. Let 𝒟 be a distribution over non-contractive embeddings of P_{n}into ultrametrics f : P_{n} → U. Then there exists x ∈ P_{n} such that _{𝒟} [|∇f (x)|_{∞} ] = Ω((logn)^{2}).

Before proving Proposition 7 we record the following numerical inequalities.

Lemma 8. The following elementary inequalities hold true:

1. For every a, b ∈ {0, 1, 2, …},

a(loga)^{2} + b(logb)^{2} (a + b) (log(a + b))^{2} − 2 [1 + log(\frac{a + b}{a})] a log(a + b).

2. For every x 1, (1 + logx) logx 4 \sqrt{x}.

Proof. The first inequality is trivial if a = 0 or b = 0, so assume that a, b 1. Denote for t 0, ψ(t) = t(logt)^{2}. Then

(a + b) (log(a + b))^{2} − b(logb)^{2} = ∫ _{b}^{a+b} ψ′(t)dt
= ∫ _{b}^{a+b} [(logt)^{2} + 2 logt]dt
a (log(a + b))^{2} + 2a log(a + b)
= a(loga)^{2} + a [log(a + b) + loga] · log(\frac{a + b}{a}) + 2a log(a + b)
a(loga)^{2} + 2 [1 + log(\frac{a + b}{a})] a log(a + b),

proving the first assertion in Lemma 8.

The second assertion in Claim 8 follows from the inequality logx 2\sqrt[4]{x} − 1, which is true since the minimum of the function y ↦ 2\sqrt[4]{y}− 1 − logy, which is attained at y = 16, is positive.

Proof of Proposition 7. We think of P_{n} as the interval of integers I = {0, …, n − 1} ⊆ . Arguing the same as in the case of the cycle C_{n}, it is enough to prove that if (U, d_{U}) is an ultrametric and f : P_{n} → U is non-contractive then

\frac{1}{n} ∑_{x=0}^{n−1} |∇f (x)|_{∞} c(logn)^{2},  (12)

where c > 0 is a universal constant.

Given a sub-interval J = {a, a+1, …, a+t} ⊆ {0, …, n−1} let m_{J} be the largest point m ∈ {a+1, …, a+t} for which d_{U}(f (m − 1), f (m)) = ∥f |_{J}∥_{Lip} = max_{1 i t} d_{U}(f (a + i − 1), f (a + i)) (if t = 0 then we set m_{J} = a). Since the distortion of J in any embedding into an ultrametric is at least |J| − 1 (see Lemma 2.4 in [31]), we know that d_{U}(f (m_{J} − 1), f (m_{J})) t = |J| − 1. We shall denote in what follows J_{s} to be the shorter of the two intervals {a, a + 1, …, m_{J} − 1} and {m_{J}, …, a + t} (breaking ties arbitrarily), and J_{b} will denote the longer of these two intervals (when |J| = 1 we use the convention J_{s} = J_{b}). Thus J = J_{s} ∪ J_{b} and |J_{s}| |J_{b}|. Finally, let x_{J} be the point in J_{s} which is closest to J_{b} (so that x_{J} ∈ {m_{J}, m_{J−1}}).

We define a function g_{J} : J → inductively as follows. If 1 |J_{s}| \sqrt{|J|}then

g_{J}(x) = \begin{cases}g_{J_{s}}(x) & if x ∈ J_{s} \ \{x_{J}\}, \\ \frac{1}{8} [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| & if x = x_{J}, \\ g_{J_{b}}(x) & if x ∈ J_{b}. \end{cases}  (13)

If, on the other hand, |J_{s}| > \sqrt{|J|}then

g_{J}(x) = \begin{cases}g_{J_{s}}(x) & if x ∈ J_{s} and |x − x_{J}| > \sqrt[4]{|J_{s}|}, \\ \frac{|J|−1}{|x−x_{J}|+1} & if x ∈ J_{s} and |x − x_{J}| \sqrt[4]{|J_{s}|}, \\ g_{J_{b}}(x) & if x ∈ J_{b}. \end{cases}  (14)

The following claim summarizes the crucial properties of the these mappings. Recall that we are using the notation I = {0, …, n − 1}.

Claim 9. The following assertions hold true for every sub-interval J ⊆ I.

1. For every x ∈ J we have g_{J}(x) |∇(f |_{J})(x)|_{∞} = max_{y∈J\\{x\}}\frac{d_{U}(f (x),f (y))}{|x−y|}.

2. For every x ∈ J, g_{J}(x) |J| − 1.

3. If |J_{s}| \sqrt{J} and |x − x_{J}| \sqrt[4]{|J_{s}|}then g_{J_{s}}(x) 4 \sqrt{|J_{s}|}.

Proof. The proofs of all of the assertions in Claim 9 will be by induction on J. To prove the first assertion assume first that 1 |J_{s}| \sqrt{|J|}. From the recursive definition in (13) it follows that we should show that \frac{1}{8} [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| |∇(f |_{J})(x_{J})|_{∞} . Since x_{J} ∈ \{m_{J} − 1, m_{J}\} the definition of m_{J} implies that |∇(f |_{J})(x_{J})|∞ |J| − 1. Thus it is enough to show that \frac{1}{8} (1 + log|J|) \sqrt{|J|}log|J| |J| − 1, which follows from the second assertion in Lemma 8. If, on the other hand, |J_{s}| > \sqrt{|J|}then from the recursive definition in (14) it follows that it is enough to show that for every x ∈ J_{s} we have \frac{|J|−1}{|x−x_{J}|+1} |∇(f |_{J})(x)|_{∞} . But since U is an ultrametric we know that

|J| − 1 d_{U}(f (m_{J} − 1), f (m_{J})) max{d_{U}(f (x), f (m_{J} − 1)), d_{U}(f (x), f (m_{J}))},

which implies the required lower bound on |∇(f |_{J})(x)|_{∞} since x_{J} ∈ {m_{J} − 1, m_{J}}. The second assertion in Claim 9 is proved similarly.

It remains to prove the third assertion in Lemma 9. Let K ⊆ J_{s} be the sub-interval of J_{s} in which the value of g_{J_{s}}(x) was first set. In other words, K ⊆ J_{s} is the smallest interval for which x ∈ K_{s} and g_{K}(x) = g_{J_{s}}(x). It follows in particular that |x − x_{K}| \sqrt[4]{|K_{s}|}. Also, by construction it is always the case that either K_{s} or K_{b} is contained in the interval [min{x_{K}, x_{J}}, max{x_{K}, x_{J}}]. Since K_{s} is shorter than K_{b} we are assured that

|K_{s}| |x_{K} − x_{J}| |x_{K} − x| + |x − x_{J}| \sqrt[4]{|K_{s}|}+ \sqrt[4]{|J_{s}|} 2\sqrt[4]{|J_{s}|}.  (15)

If |K_{s}| \sqrt{|K|}then necessarily x = x_{K} and g_{K}(x) was determined by the second line in (13). Hence

g_{J_{s}}(x) = g_{K}(x) = \frac{1}{8} [1 + log(\frac{|K|}{|K_{s}|})] |K_{s}| log|K| \frac{1}{4} [1 + log|J_{s}|] \sqrt[4]{|J_{s}|}log|J_{s}| 4 \sqrt{|J_{s}|},  (16)

where we used (15) and the last inequality in (16) follows from the second assertion of Lemma 8. Otherwise |K_{s}| > \sqrt{|K|}and g_{K}(x) was determined by the second line in (14), i.e.

g_{J_{s}}(x) = g_{K}(x) = \frac{|K| − 1}{|x − x_{K}| + 1} < |K| < |K_{s}|^{2} 4 \sqrt{|J_{s}|},

where we used (15). This completes the proof of Claim 9.

With Claim 9 at hand we are in position to conclude the proof of Proposition 7. We will prove by induction on |J| that

∑_{x∈J} g_{J}(x) c|J|(log|J|)^{2}.  (17)

This will prove (12), and hence imply Proposition 7, since by the first assertion of Claim 9 we get that

∑_{x=0}^{n−1} |∇f (x)|_{∞} ∑_{x∈I} g_{I}(x) cn(logn)^{2}.

Inequality (17) trivially holds true with small enough constant c if |J| 2^{60}, so assume that |J| > 2^{60}. To prove (17) we distinguish between two cases. If |J_{s}| \sqrt{|J|}then since g_{J_{s}}(x_{J}) |J_{s}| (by the second assertion in Claim 9) we see by induction that

∑_{x∈J} g_{J}(x) = ∑_{x∈J_{s}} g_{J_{s}}(x) + ∑_{x∈J_{b}}g_{J_{b}}(x) + g_{J}(x_{J}) − g_{J_{s}}(x_{J})

> c (|J_{s}|(log|J_{s}|)^{2} + |J_{b}|(log|J_{b}|)^{2})+ 2 [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| − |J_{s}|  (18)
c|J|(log|J|)^{2} − 2c [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| + [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J|  (19)
c|J|(log|J|)^{2},  (20)

where in (18) we used the inductive hypothesis and the inductive definition in (13) , in (19) we used Lemma 8, and (20) holds for c \frac{1}{2}.

On the other hand if |J_{s}| > \sqrt{|J|}then

∑_{x∈J} g_{J}(x) = ∑_{x∈J_{s}} g_{J_{s}}(x) + ∑_{x∈J_{b}}g_{J_{b}}(x) + ∑_{\begin{matrix}x∈J_{s} \\ |x−x_{J}| \sqrt[4]{|J_{s}|} \end{matrix}}(\frac{|J| − 1}{|x − x_{J}| + 1} − g_{J_{s}}(x))  (21)

c|J|(log|J|)^{2} − 2c [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| + \begin{aligned}⌊ & \sqrt[4]{|J_{s}|} & ⌋ \\ & ∑ \\ & k=0 \end{aligned} \frac{|J| − 1}{k + 1} − 8|J_{s}|^{3/4}  (22)

c|J|(log|J|)^{2} − 2c [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| + \frac{1}{4}(|J| − 1) log|J_{s}| − 8|J|^{3/4}
c|J|(log|J|)^{2} − 2c [1 + log(\frac{|J|}{|J_{s}|})] |J_{s}| log|J| + \frac{1}{8}(|J| − 1) log|J_{s}|  (23)
c|J|(log|J|)^{2},  (24)

where in (21) we used the inductive definition in (14), in (22) we used the inductive hypothesis, Lemma 8 and Claim 9, and inequalities (23) and (24) hold for |J| > 2^{60} and small enough c, respectively, since \frac{|J|}{2} |J_{s}| > \sqrt{|J|}. This completes the proof of Proposition 7.

We now pass to the proof of the lower bound in Theorem 1in its full strength, i.e. in the case of maximum gradient embeddings into trees. We start by describing the diamond graphs {G_{k}}_{k=1}^{∞}, and a special labelling of them that we will use throughout the ensuing arguments. The first diamond graph G_{1} is a cycle of length 4, and G_{k+1} is obtained from G_{k} by replacing each edge by a quadrilateral. Thus G_{k} has 4^{k} edges and \frac{2·4^{k}+4}{3} vertices. As we have done before, the required lower bound on maximum gradient embeddings of G_{k} into trees will be proved if we show that for every tree T and every non-contractive embedding f : G_{k} → T we have

\frac{1}{4^{k}} ∑_{e∈E(G_{k})} ∑_{x∈e} |∇f (x)|_{∞} = Ω (k^{2}).  (25)

Note that the inequality (25) is different from the inequalities that we proved in the case of the cycle and the path in that the weighting on the vertices of G_{k} that it induces is not uniform— high degree vertices get more weight in the average in the left-hand side of (25).

We will prove (25) by induction on k. In order to facilitate such an induction, we will first strengthen the inductive hypothesis. To this end we need to introduce a useful labelling of G_{k}. For 1 i k the graph G_{k} contains 4^{k−i} canonical copies of G_{i}, which we index by elements of {1, 2, 3, 4}^{k−i}, and denote {G_{[α]}^{(k)}}_{α∈{1,2,3,4}^{k−i}}. These graphs are defined as follows—see Figures 1 and 2 for a schematic description.

Figure 1: The graph G_{2} and the labelling of the canonical copies of G_{1} contained in it.

Figure 2: The graph G_{3} and the induced labelling of canonical copies of G_{1} and G_{2}.

Formally, we set G_{[∅]}^{(k)} = G_{k}, and assume inductively that the canonical subgraphs of G_{k−1} have been defined. Let H_{1}, H_{2}, H_{3}, H_{4} be the top-right, top-left, bottom-right and bottom-left copies of G_{k−1} in G_{k}, respectively. For α ∈ {1, 2, 3, 4}^{k−1−i} and j ∈ {1, 2, 3, 4} we denote the copy of G_{i} in H_{j} corresponding to G_{[α]}^{(k−1)} by G_{[jα]}^{(k)} .

For every 1 i k and α ∈ {1, 2, 3, 4}^{k−i} let T_{[α]}^{(k)}, B_{[α]}^{(k)}, L_{[α]}^{(k)}, R_{[α]}^{(k)} be the topmost, bottom-most, left-most, and right-most vertices of G_{[α]}^{(k)}, respectively. We will construct inductively a set of simple cycles 𝒞_{[α]} in G_{[α]}^{(k)} and for each C ∈ 𝒞_{[α]} an edge ε_{C} ∈ E (𝒞_{[α]}), with the following properties.

1. The cycles in 𝒞_{[α]} are edge-disjoint, and they all pass through the vertices T_{[α]}^{(k)}, B_{[α]}^{(k)}, L_{[α]}^{(k)}, R_{[α]}^{(k)}. There are 2^{i−1} cycles in 𝒞_{[α]}, and each of them contains 2^{i+1} edges. Thus in particular the cycles in 𝒞_{[α]} form a disjoint cover of the edges in G_{[α]}^{(k)}.

2. If C ∈ 𝒞_{[α]} and ε_{C} = \{x, y\} then d_{T}(f (x), f (y)) \frac{2^{i+1}}{3} − 1.

3. Denote E_{[α]} = {ε_{C} : C ∈ 𝒞_{[α]}} and Δ_{i} = ⋃ _{α∈{1,2,3,4}^{k−i}}E_{[α]}. The edges in Δ_{i} will be called the designated edges of level i. For α ∈ {1, 2, 3, 4}^{k−i}, C ∈ 𝒞_{[α]} and j < i let Δ_{j}(C) = Δ_{j} ∩ E(C) be the designated edges of level j on C. Then we require that each of the two paths T_{[α]}^{(k)} − L_{[α]}^{(k)} − B_{[α]}^{(k)} and T_{[α]}^{(k)} − R_{[α]}^{(k)} − B_{[α]}^{(k)} in C contains exactly 2^{i−j−1} edges from Δ_{j}(C).

The construction is done by induction on i. For i = 1 and α ∈ {1, 2, 3, 4}^{k−1} we let 𝒞_{[α]} contain only the 4-cycle G_{[α]}^{(k)} itself. Moreover by Lemma 6 there is and edge ε_{G_{[α]}^{(k)}} ∈ E (G_{[α]}^{(k)})such that if ε_{G_{[α]}^{(k)}} = {x, y} then

d_{T}(f (x), f (y)) \frac{1}{3}. This completes the construction for i = 1. Assuming we have completed the construction for i − 1 we construct the cycles at level i as follows. Fix arbitrary cycles C_{1} ∈ 𝒞_{[1α]}, C_{2} ∈ 𝒞_{[2α]}, C_{3} ∈ 𝒞_{[3α]}, C_{4} ∈ 𝒞_{[4α]}. We will use these four cycles to construct two cycles in 𝒞_{[α]}. The first one consists of the T_{[α]}^{(k)} − R_{[α]}^{(k)} path in C_{1} which contains the edge ε_{C_{1}}, the R_{[α]}^{(k)} − B_{[α]}^{(k)} path in C_{3} which does not contain the edge ε_{C_{3}}, the B_{[α]}^{(k)} − L_{[α]}^{(k)} path in C_{4} which contains the edge ε_{C_{4}}, and the L_{[α]}^{(k)} − T_{[α]}^{(k)} path in C_{2} which does not contain the edge ε_{C_{2}}. The remaining edges in E(C_{1}) ∪ E(C_{2}) ∪ E(C_{3}) ∪ E(C_{4}) constitute the second cycle that we extract from C_{1}, C_{2}, C_{3}, C_{4}. Continuing in this manner by choosing cycles from 𝒞_{[1α]} \ {C_{1}}, 𝒞_{[2α]} \ {C_{2}}, 𝒞_{[3α]} \ {C_{3}}, 𝒞_{[4α]} \ {C_{4}} and repeating this procedure, and then continuing until we exhaust the cycles in 𝒞_{[1α]} ∪ 𝒞_{[2α]} ∪ 𝒞_{[3α]} ∪ 𝒞_{[4α]}, we obtain the set of cycles 𝒞_{α}. For every C ∈ 𝒞_{α} we then apply Lemma 6 to obtain an edge ε_{C} with the required property.

For each edge e ∈ E(G_{k}) let α ∈ {1, 2, 3, 4}^{k−i} be the unique multi-index such that e ∈ E (G_{[α]}^{(k)}). We denote by C_{i}(e) the unique cycle in 𝒞_{[α]} containing e. We will also denote ê_{i}(e) = ε_{C_{i}(e)}. Finally we let a_{i}(e) ∈ e and b_{i}(e) ∈ ê_{i}(e) be vertices such that

d_{T}(f (a_{i}(e)), f (b_{i}(e))) = max_{\begin{matrix}a∈e \\ b∈ê_{i}(e) \end{matrix}}d_{T}(f (a), f (b)).

Note that by the definition of ê_{i}(e) and the triangle inequality we are assured that

d_{T}(f (a_{i}(e)), f (b_{i}(e))) \frac{1}{2} (\frac{2^{i+1}}{3} − 1) \frac{2^{i}}{12}.  (26)

Recall that we plan to prove (25) by induction on k. Having done all of the above preparation, we are now in position to strengthen (25) so as to make the inductive argument easier. Given two edges e, h ∈ G_{k} we write e ⌢_{i} h if both e, h are on the same canonical copy of G_{i} in G_{k}, C_{i}(e) = C_{i}(h) = C, and furthermore e and h on the same side of C. In other words, e ⌢_{i} h if there is α ∈ {1, 2, 3, 4}^{k−i} and C ∈ 𝒞_{[α]} such that if we partition the edges of C into two disjoint T_{[α]}^{(k)} − B_{[α]}^{(k)} paths, then e and h are on the same path.

Let m ∈ be a universal constant that will be specified later. For every integer ℓ k/m and any α ∈ {1, 2, 3, 4}^{k−mℓ} define

L_{ℓ}(α) = \frac{1}{4^{mℓ}} ∑_{e∈E(G_{[α]}^{(k)})} max_{\begin{matrix}i∈\{1,...,ℓ\} \\ e⌢_{im}ê_{im}(e) \end{matrix}} \frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} .

We also write L_{ℓ} = min_{α∈{1,2,3,4}^{k−mℓ}}L_{ℓ}(α). We will prove that L_{ℓ} L_{ℓ−1} + cℓ, where c > 0 is a universal constant. This will imply that for ℓ = ⌊k/m⌋ we have L_{ℓ} = Ω(k^{2}) (since m is a universal constant). By simple arithmetic (25) follows.

Observe that for every α ∈ {1, 2, 3, 4}^{k−mℓ} we have

L_{ℓ}(α) = \frac{1}{4^{m}} ∑_{β∈\{1,2,3,4\}^{m}}\frac{1}{4^{m(ℓ−1)}} ∑_{e∈E(G_{[βα]}^{(k)})} max_{\begin{matrix}i∈\{1,...,ℓ\} \\ e⌢_{im}ê_{im}(e) \end{matrix}} \frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1}

= \frac{1}{4^{m}} ∑_{β∈\{1,2,3,4\}^{m}}\frac{1}{4^{m(ℓ−1)}} ∑_{e∈E(G_{[βα]}^{(k)})} max_{\begin{matrix}i∈\{1,...,ℓ−1\} \\ e⌢_{im}ê_{im}(e) \end{matrix}}\frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1}

+\frac{1}{4^{mℓ}} ∑_{e∈E(G_{[α]}^{(k)})}max \{0, \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} · 1_{\{e⌢_{ℓm}ê_{ℓm}(e)\}}

− max_{\begin{matrix}i∈\{1,...,ℓ−1\} \\ e⌢_{im}ê_{im}(e) \end{matrix}}\frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \}

= \frac{1}{4^{m}} ∑_{β∈\{1,2,3,4\}^{m}}L_{ℓ−1}(βα)

+\frac{1}{4^{mℓ}} ∑_{e∈E(G_{[α]}^{(k)})}max \{0, \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} · 1_{\{e⌢_{ℓm}ê_{ℓm}(e)\}}

− max_{\begin{matrix}i∈\{1,...,ℓ−1\} \\ e⌢_{im}ê_{im}(e) \end{matrix}}\frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \}

L_{ℓ−1} + \frac{1}{4^{mℓ}} ∑_{e∈E(G_{[α]}^{(k)})}max \{0, \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} · 1_{\{e⌢_{ℓm}ê_{ℓm}(e)\}}

− max_{\begin{matrix}i∈\{1,...,ℓ−1\} \\ e⌢_{im}ê_{im}(e) \end{matrix}}\frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \} .

Thus it is enough to show that

A =^{def} \frac{1}{4^{mℓ}} ∑_{e∈E(G_{[α]}^{(k)})}max \{0, \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} · 1_{\{e⌢_{ℓm}ê_{ℓm}(e)\}}

− max_{\begin{matrix}i∈\{1,...,ℓ−1\} \\ e⌢_{im}ê_{im}(e) \end{matrix}}\frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \} = Ω(ℓ). (27)

To prove (27) denote for C ∈ 𝒞_{[α]} S_{C} = {e ∈ E(C) : ε_{C} ⌢_{ℓm}e and

max_{\begin{matrix}i∈\{1,...,ℓ−1\} \\ e⌢_{im}ê_{im}(e) \end{matrix}}\frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \frac{1}{2} · \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} \} .

Then using (26) we see that

A  \frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{\begin{matrix}e∈E(C)\S_{C} \\ ε_{C}⌢_{ℓm}e \end{matrix}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1}
\frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{\begin{matrix}e∈E(C) \\ ε_{C}⌢_{ℓm}e \end{matrix}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} − \frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{e∈S_{C}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1}
\frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{i=1}^{2^{mℓ−1}} \frac{2^{mℓ}}{12i} − \frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{e∈S_{C}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1}
= Ω (\frac{1}{4^{mℓ}} · |𝒞_{[α]}| · 2^{mℓ}· mℓ) − \frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{e∈S_{C}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1}
= Ω(mℓ) − \frac{1}{2 · 4^{mℓ}} ∑_{C∈𝒞_{[α]}} ∑_{e∈S_{C}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1} .  (28)

To estimate the negative term in (28) fix C ∈ 𝒞_{[α]}. For every edge e ∈ S_{C} (which implies in particular that ê_{ℓm}(e) = ε_{C}) we fix an integer i < ℓ such that e ⌢_{im} ê_{im}(e) and

\frac{2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \frac{d_{T}(f (a_{im}(e)), f (b_{im}(e))) ∧ 2^{im}}{d_{G_{k}}(e,ê_{im}(e)) + 1} \frac{1}{2} · \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1}

\frac{1}{12} · \frac{2^{ℓm}}{d_{G_{k}}(e, ε_{C}) + 1},

or

d_{G_{k}}(e,ê_{im}(e)) + 1 2^{(i−ℓ)m+4} [d_{G_{k}}(e, ε_{C}) + 1].  (29)

We shall call the edge ê_{im}(e) the designated edge that inserted e into S_{C}. For a designated edge ε ∈ E(C) of level im (i.e. ε ∈ Δ_{im}(C)) we shall denote by ℰ_{C}(ε) the set of edges of C which ε inserted to S_{C}. Denoting D_{ε} = d_{G_{k}}(ε, ε_{C}) + 1 we see that (29) implies that for e ∈ ℰ_{C}(ε) we have

|D_{ε} − [d_{G_{k}}(e, ε_{C}) + 1] | 2^{(i−ℓ)m+4} [d_{G_{k}}(e, ε_{C}) + 1].  (30)

Assuming that m 5 we are assured that 2^{(i−ℓ)m+4} \frac{1}{2}. Thus (30) implies that

\frac{D_{ε}}{1 + 2^{(i−ℓ)m+4}} d_{G_{k}}(e, ε_{C}) + 1 \frac{D_{ε}}{1 − 2^{(i−ℓ)m+4}} .

Hence

∑_{e∈S_{C}} \frac{d_{T}(f (a_{ℓm}(e)), f (b_{ℓm}(e))) ∧ 2^{ℓm}}{d_{G_{k}}(e,ê_{ℓm}(e)) + 1}  ∑_{i=1}^{ℓ−1} ∑_{ε∈Δ_{im}(C)} ∑_{e∈ℰ_{C}(ε)} \frac{2^{ℓm}}{d_{G_{k}}(e, ε_{C}) + 1}

2 ∑_{i=1}^{ℓ−1} ∑_{ε∈Δ_{im}(C)} ∑_{\begin{matrix}j∈ \\ \frac{Dε}{1+2^{(i−ℓ)m+4}} j \frac{Dε}{1−2^{(i−ℓ)m+4}} \end{matrix}} \frac{2^{ℓm}}{j}

= O(1) · 2^{ℓm}∑_{i=1}^{ℓ−1} |Δ_{im}(C)| · log(\frac{1 + 2^{(i−ℓ)m+4}}{1 − 2^{(i−ℓ)m+4}} )
= O(1) · 2^{ℓm}ℓ · 2^{(ℓ−i)m} · 2^{(i−ℓ)m} = O(1) · 2^{ℓm}ℓ.

Thus, using (28) we see that

A = Ω(mℓ) − O(1) · \frac{1}{4^{ℓm}} · |𝒞_{[α]} | 2^{mℓ}ℓ = Ω(mℓ) − O(1)ℓ = Ω(ℓ),

provided that m is a large enough absolute constant.

This completes the proof of the lower bound in Theorem 1.

4 Monotone clustering problems

In this section we give some examples which illustrate how certain monotone clustering problems can be solved efficiently on ultrametrics. Our arguments are quite flexible, and apply in more general situations. Before passing to these algorithms, we make a few general remarks on the framework for monotone clustering that was discussed in the introduction.

In the definition of monotone clustering we required that Γ(x, d, P) is homogeneous in d. One might wonder whether it is possible to consider also higher orders of homogeneity, i.e. clustering cost functions Γ which satisfy Γ(x, λd, P) = λ^{p}Γ(x, d, P) for some p > 1 (this occurs, for example, in the k-means clustering problem, where the goal is to find k “centers” that minimize the sum over the data points of the squared distance to the closest center). For the proof of Theorem 2 to work in this setting we need a distribution over non-contractive embeddings into ultrametrics f : X → U with a polylogarithmic upper bound on the expected value of |∇f (x)|_{∞}^{p} . Unfortunately, this is impossible to achieve in general. Indeed, let f : C_{n} → T be a random non-contractive embedding of the n-cycle into trees. Lemma 6 implies that there exists an edge (x, x + 1) ∈ E(C_{n}) for which d_{T}(f (x), f (x + 1)) \frac{n}{3} − 1. Thus

∑_{\{x,y\}∈E(C_{n})}d_{T}(f (x), f (y))^{p} \frac{n^{p}}{12^{p}}.

Taking expectation we see that

max_{x∈V(C_{n})} [|∇f (x)|_{∞}^{p} ] \frac{1}{n} ∑_{x∈V(C_{n})} [|∇f (x)|_{∞}^{p} ] \frac{n^{p−1}}{12^{p}} .

We note, however, that the proof of Theorem 2 used the homogeneity of Γ in a weak way. In order to get a polylogarithmic reduction to ultrametrics is enough to assume, for example, that for every λ 1 we have Γ(x, λd, P) = O (polylog(n))· λ · Γ(x, d, P).

Our second remark concerns the fact that the solution space for monotone clustering problem that was presented in the introduction was 2^{X×2^{X}}. This is a huge space, and as we have seen in Section 1.1, by setting the clustering cost function to be ∞ on certain possible clustering solutions it is possible to reduce the size of this space. Additionally, in the arguments is Section 1.1 the cost function Γ ignored the structure of the solution space. Thus in a more generic formulation of the monotone clustering framework we can assume that the solution space is some abstract finite set S(X). For example, in our version of the fault-tolerant k-median problem we can take the solution space to be \binom{X}{k}.

4.1 Monotone clustering on ultrametrics via dynamic programming

We now pass to the design of some monotone clustering algorithms on ultrametrics. It is a standard fact (see for example [6]) that any ultrametric (U, d_{U}) can be represented as follows. There is a graph theoretical tree T = (V, E) such that U is the set of leaves of T. The vertices of T are labelled by Δ : V → [0, ∞) and for every u, v ∈ U we have d_{U}(u, v) = Δ(lca(u, v)), where lca(u, v) is the least common ancestor of u and v in T. We may, and will, assume in what follows that every vertex of T is either a leaf or has exactly two children.

We begin by showing that the fault-tolerant version of the k-median problem described in (5) can be solved exactly on ultrametrics.

Lemma 10. The minimization of the objective function in (5) can be solved exactly on any n-point ultrametric in time O(kn^{2}).

Proof. Let (U, d_{U}) be an n-point ultrametric and let T = (V, E) be a binary tree with vertex labels Δ : V → [0, ∞) which represents U. We also assume that we are given fault-tolerant parameters {j(u)}_{u∈U}. For every v ∈ V let T_{v} denote the subtree of T rooted at v. Define for v ∈ V and s ∈ {0, …, k}

cost^{∗}(v, s) = min \{ ∑_{\begin{matrix}x∈T_{v}∩U \\ j(x) s \end{matrix}} d_{U} (x, x_{j(x)}^{∗}(x; d_{U})): x_{1}, x_{2}, …, x_{s} ∈ T_{v} ∩ U\}.  (31)

Our goal is to compute cost^{∗}(r, k), where r is the root of T. This will be done using dynamic programming. For any leaf u ∈ U and s ∈ {0, …, k} define cost(u, s) = 0. Let v ∈ V be an internal vertex with two children u, w ∈ V. Define recursively

cost(v, s) = min_{t∈{0,...,s}}[cost(u, t) + cost(w, s − t)

+ Δ(v) · (|{x ∈ T_{u} ∩ U : t < j(x) s}| + |{x ∈ T_{w} ∩ U : s − t < j(x) s}|)]. (32)

A bottom-up computation of the dynamic program in (32) computes cost(v, s) naïvely in O(kn^{2}) time. We will be done if we show that cost(v, s) = cost^{∗}(v, s) for any v ∈ V and s ∈ {0, …, k}. The fact that cost^{∗}(v, s) cost(v, s) is obvious since (32) computes a feasible solution of (31) (this fact is proved by a straightforward induction).

We prove the reverse inequality by induction on |T_{v}|. Let x_{1}, …, x_{s} ∈ T_{v} ∩ U be such that

cost^{∗}(v, s) = ∑_{\begin{matrix}x∈T_{v}∩U \\ j(x) s \end{matrix}} d_{U} (x, x_{j(x)}^{∗}(x; d_{U})).

Let u, w be the children of v in T. We may reorder the points so that for some t ∈ {0, …, s} we have {x_{1}, …, x_{t}} = T_{u} ∩ {x_{1}, …, x_{s}} and {x_{t+1}, …, x_{s}} = T_{w} ∩ {x_{1}, …, x_{s}}. Then

cost^{∗}(v, s) = ∑_{\begin{matrix}x∈T_{v}∩U \\ j(x) s \end{matrix}} d_{U} (x, x_{j(x)}^{∗}(x; d_{U}))

= ∑_{\begin{matrix}x∈T_{u}∩U \\ j(x) t \end{matrix}} d_{U} (x, x_{j(x)}^{∗}(x; d_{U}))+ ∑_{\begin{matrix}x∈T_{w}∩U \\ j(x) s−t \end{matrix}} d_{U} (x, x_{j(x)}^{∗}(x; d_{U}))

+Δ(v) · (|{x ∈ T_{u} ∩ U : t < j(x) s}| + |{x ∈ T_{w} ∩ U : s − t < j(x) s}|)  (33)
cost^{∗}(u, t) + cost^{∗}(w, s − t)
+Δ(v) · (|{x ∈ T_{u} ∩ U : t < j(x) s}| + |{x ∈ T_{w} ∩ U : s − t < j(x) s}|)  (34)
cost(u, t) + cost(w, s − t)
+Δ(v) · (|{x ∈ T_{u} ∩ U : t < j(x) s}| + |{x ∈ T_{w} ∩ U : s − t < j(x) s}|)  (35)
cost(v, s),  (36)

where in (33) we used the fact that the tree T represents the ultrametric (U, d_{U}), in (34) we used the definition of cost^{∗}(u, t) and cost^{∗}(w, s − t) given by (31), in (35) we used the inductive hypothesis, and in (36) we used (32).

Our final result is the proof of Lemma 3, which yields a FPTAS for the Σℓ_{p} clustering problem on ultrametrics. We start with the following inequality.

Lemma 11. Fix p 1 and assume that a_{1} a_{2} ⋯ a_{n} 0 and b_{1}, …, b_{n} 0. Then

∑_{j=1}^{n} (a_{j}^{p} + b_{j}^{p})^{1/p} ∑_{j=2}^{n} a_{j} + (a_{1}^{p} + ∑_{j=1}^{n} b_{j}^{p})^{1/p}.

Proof. The proof is by induction on n, and the inductive hypothesis simplifies to

(a_{1}^{p} + ∑_{j=1}^{n} b_{j}^{p})^{1/p} − a_{n+1} (a_{1}^{p} + ∑_{j=1}^{n+1} b_{j}^{p})^{1/p} − (a_{n+1}^{p} + b_{n+1}^{p})^{1/p}.  (37)

Denote for x 0

f (x) = (a_{1}^{p} + ∑_{j=1}^{n} b_{j}^{p} + x)^{1/p} − (a_{n+1}^{p} + x)^{1/p}.

Inequality (37) is f (b_{n+1}^{p}) f (0), so it is enough to prove that f is decreasing. But

f′(x) = \frac{1}{p (a_{1}^{p} + ∑ _{j=1}^{n} b_{j}^{p} + x)^{1−1/p}} − \frac{1}{p (a_{n+1}^{p} + x)^{1−1/p}} \frac{1}{p (a_{1}^{p} + x)^{1−1/p}} − \frac{1}{p (a_{n+1}^{p} + x)^{1−1/p}} 0,

since a_{1} a_{n+1}.

Proof of Lemma 3. Let (U, d_{U}) be an n-point ultrametric and let T = (V, E) be a binary tree with vertex labels Δ : V → [0, ∞) which represents U. For v ∈ V, ℓ ∈ {0, …, k}, s ∈ {0, …, n} and t ∈ [0, ∞) define B^{∗}(v, ℓ, s, t) to be the minimum cost according to (7) to cluster T_{v}∩ U using ℓ sets and centers, when we are allowed to exclude s points from T_{v} ∩ U, and the most costly cluster has cost t.

We next define a “pseudo cost” B(v, ℓ, s, t) inductively as follows. If v is a leaf then define B(v, 1, 0, 0) = B(v, 1, 1, 0) = B(v, 0, 1, 0) = 0, and for all other values of ℓ, s, t we set B(v, ℓ, s, t) = ∞. When v has children u and w define:

B(v, ℓ, s, t) = min {B(u, ℓ_{1}, s_{1}, t_{1}) + B(w, ℓ_{2}, s_{2}, t_{2})

+ (t_{1}^{p} + r_{2}Δ(v)^{p})^{1/p} − t_{1} + (t_{2}^{p} + r_{1}Δ(v)^{p})^{1/p} − t_{2} : \begin{matrix}s_{1},r_{1},s_{2},r_{2}∈\{0,...,s\}, \\ t_{1},t_{2}∈[0,t], \\ ℓ_{1}∈\{0,...,ℓ\}, \\ r_{1} s_{1}, \\ r_{2} s_{2}, \\ s=s_{1}+s_{2}−r_{1}−r_{2}, \\ ℓ=ℓ_{1}+ℓ_{2}, \\ t=max\{(t_{1}^{p}+r_{2}Δ(v)^{p})^{1/p}, (t_{2}^{p}+r_{1}Δ(v)^{p})^{1/p}\} \end{matrix}\} .

With these definition we will prove the following claim by induction.

Claim 12. For every v ∈ T, ℓ ∈ {0, …, k}, s ∈ {0, …, n} and t ∈ [0, ∞) we have

B^{∗}(v, ℓ, s, t) = B(v, ℓ, s, t).

Assuming the validity of Claim 12 for the moment, we conclude as follows. The dynamic programming algorithm described above does not suffice since the parameter t takes values in the range [0, ∞), while we need it to take only poly(n) values. We fix this issue using an argument which is based on ideas from [5].

Normalize the distances in U so that the minimum distance is 1, and denote Φ = diam(U). We can clearly assume that t nΦ. Assume first of all that we can ensure that t A = O (poly(n)). Once this is achieved then all we need to do is to apply a standard discretization procedure as follows. Fix an integer M > 0 which will be determined presently and let A′ = {0, A/M, 2A/M, …, A}. For t ∈ [0, A] denote by rd(t) the rounding of t to its closest value in A′. We can now define a discretized dynamic programming procedure B′(v, ℓ, s, τ), where v, ℓ, s take the same values as in the definition of B(v, ℓ, s, t) and τ ∈ A′. This is done by defining as before for a leaf v ∈ U B(v, 1, 0, 0) = B(v, 1, 1, 0) = B(v, 0, 1, 0) = 0, and for all other values of ℓ, s, τ setting B(v, ℓ, s, τ) = ∞. When v has children u and w define:

B′(v, ℓ, s, τ) = min {rd((τ_{1}^{p} + r_{2}Δ(v)^{p})^{1/p} − τ_{1} + (τ_{2}^{p} + r_{1}Δ(v)^{p})^{1/p} − τ_{2})

+ B′(u, ℓ_{1}, s_{1}, τ_{1}) + B′(w, ℓ_{2}, s_{2}, τ_{2}) : \begin{matrix}s_{1},r_{1},s_{2},r_{2}∈\{0,...,s\}, \\ τ_{1},τ_{2}∈A′, \\ ℓ_{1}∈\{0,...,ℓ\}, \\ r_{1} s_{1}, \\ r_{2} s_{2}, \\ s=s_{1}+s_{2}−r_{1}−r_{2}, \\ ℓ=ℓ_{1}+ℓ_{2}, \\ τ=rd(max\{(τ_{1}^{p}+r_{2}Δ(v)^{p})^{1/p}, (τ_{2}^{p}+r_{1}Δ(v)^{p})^{1/p}\}) \end{matrix}\} .

It is straightforward to check by induction that for any v ∈ V, ℓ ∈ {0, …, k}, s ∈ {0, …, n} and t ∈ [0, A] we have

|B(v, ℓ, s, t) − B′(v, ℓ, s, rd(t))| \frac{4|T_{v}|}{M}.

Since the optimal value of the Σℓ_{p} clustering problem is at least 1 (excluding trivial cases), as this is the smallest distance in U, B′will yield an approximation algorithm for this problem whose multiplicative error is bounded by 1 + O(n/M). Taking M = n/ε for some ε ∈ (0, 1) we obtain the required PTAS.

We therefore need to argue that we can ensure that t = O(poly(n)). Recall that we can assume that t nΦ. Let P = {(x_{1}, C_{1}), …, (x_{k}, C_{k})} be the (yet unknown) optimal solution of the Σℓ_{p} clustering problem with k-centers on U. Let h be the maximum length appearing in the solution, i.e. h = max_{1 i k} max_{x∈C_{i}} d_{U}(x_{i}, x). Fix ε ∈ (0, 1) and define two “levels” of the tree T by

L = {v ∈ V : Δ(v) h < Δ(parent(v))},

and

Q = \{v ∈ V : Δ(v) \frac{εh}{n^{2}} < Δ(parent(v))\} .

Let T′be the subtree obtained from T by deleting the subtrees {T_{v} \ {v}}_{v∈Q}, and let U′denote the leaves of T′. Equivalently, U′is obtained from U by contracting all distances smaller that εh/n^{2}. It is straightforward to check that cost_{U′}(P) cost_{U}(P) (1 + ε) cost_{U′}(P).

Note that for every v ∈ L the aspect ratio (i.e. the ratio of the diameter and the shortest distance) of T′_{v}∩U′is at most n^{2}/ε. So, by the above reasoning (in the case of an a priori polynomial bound on t) we can approximate in polynomial time the value of B^{∗}(v, ℓ, s, t) up to a factor 1 + O(ε). It remains to “glue” these approximate solutions to a solution of the Σℓ_{p} clustering problem on T. This is done by a (simpler) dynamic programming argument as follows. Denote by T̂ the subtree of T′ whose root is the same as that of T′ and whose leaves are L. For v ∈ T̂ let C^{∗}(v, ℓ) be the optimal solution of the Σℓ_{p} clustering problem on T̂_{v}with ℓ centers and assuming that the largest distance appearing in the solution is at most h. We calculate C^{∗}(v, ℓ) by dynamic programming: For v ∈ L define C(v, ℓ) = min_{t}B^{∗}(v, ℓ, 0, t), and if v has two children u, w in T̂ then

C(v, ℓ) = min{C(u, ℓ_{1}) + C(w, ℓ_{2}) : ℓ_{1} ∈ {0, …, ℓ}, ℓ_{1} + ℓ_{2} = ℓ} .

A straightforward induction shows that C^{∗}(v, ℓ) = C(v, ℓ).

The only thing that is left to be explained is how to find the value h. This is done by exhaustive search: We try all the \binom{n}{2} possible values of h, do the above procedure for each of them, and take the minimum of the values that we get.

The proof of Lemma 3 will be complete once we prove Claim 12. We first note that B^{∗}(v, ℓ, s, t) B(v, ℓ, s, t). This is true because B(·) represents a feasible solution of B^{∗}(·). The proof of this fact is by induction. If u, w ∈ V are the children of v in T then there exist s_{1}, s_{2}, t_{1}, t_{2}, r_{1}, r_{2}, ℓ_{1}, ℓ_{2} such that

B(v, ℓ, s, t) = B(u, ℓ_{1}, s_{1}, t_{1}) + B(w, ℓ_{2}, s_{2}, t_{2}) + (t_{1}^{p} + r_{2}Δ(v)^{p})^{1/p} − t_{1} + (t_{2}^{p} + r_{1}Δ(v)^{p})^{1/p} − t_{2},

where s_{1}, r_{1}, s_{2}, r_{2} ∈ {0, …, s}, t_{1}, t_{2} ∈ [0, t], ℓ_{1} ∈ {0, …, ℓ}, r_{1} s_{1}, r_{2} s_{2}, s = s_{1} + s_{2} − r_{1} − r_{2}, ℓ = ℓ_{1} + ℓ_{2}, and t = max{(t_{1}^{p} + r_{2}Δ(v)^{p})^{1/p}, (t_{2}^{p} + r_{1}Δ(v)^{p})^{1/p}}. By the inductive hypothesis B(u, ℓ_{1}, s_{1}, t_{1}) and B(w, ℓ_{2}, s_{2}, t_{2}) correspond to feasible solutions of B^{∗}(·) on T_{u} ∩ U and T_{w} ∩ U, respectively. Hence B(v, ℓ, s, t) corresponds to the following feasible solution: Take the union of the centers in T_{u} ∩ U and T_{w}∩U and retain all the current clusters in T_{u}∩U and T_{w}∩U as is. Next add arbitrary r_{1} unclustered points from T_{u}∩ U (from the pool of s_{1} unclustered points that we are assuming exist in T_{u}∩ U) to the cluster with the most weight in T_{w}∩ U, and similarly add r_{2} unclustered points from T_{w}∩ U to the cluster with the most weight in T_{u} ∩ U. This creates the required feasible solution.

We next prove by induction that B^{∗}(v, ℓ, s, t) B(v, ℓ, s, t). Consider the clustering solution at which B^{∗}(v, ℓ, s, t) is attained. It corresponds to s excluded leaves y_{1}, …, y_{s} ∈ T_{v} ∩ U, ℓ “centers” x_{1}, …, x_{ℓ} ∈ (T_{v} ∩ U) \ {y_{1}, …, y_{s}} and a partition {C_{1}, …, C_{ℓ}} of (T_{v} ∩ U) \ {y_{1}, …, y_{s}} such that

B^{∗}(v, ℓ, s, t) = ∑_{j=1}^{ℓ} (∑_{x∈C_{j}} d(x, x_{j})^{p})^{1/p}.

By reordering the points we may assume that x_{1}, …, x_{ℓ_{1}} ∈ T_{u} and x_{ℓ_{1}+1}, …, x_{ℓ_{1}+ℓ_{2}}, ∈ T_{w} (where ℓ_{2} = ℓ −ℓ_{1}). Denote

|(⋃_{j=1}^{ℓ_{1}} C_{j} )∩ T_{w}| = r_{2} and |( ⋃_{j=ℓ_{1}+1}^{ℓ_{1}+ℓ_{2}} C_{j} )∩ T_{u}| = r_{1}.

Finally, we may assume that

t_{1} =^{def} ∑_{x∈C_{1}∩T_{u}}d(x, x_{1})^{p} = max_{j∈{1,...,ℓ_{1}}} ∑_{x∈C_{j}∩T_{u}}d(x, x_{j})^{p},

and

t_{2} =^{def} ∑_{x∈C_{ℓ_{1}+1}∩T_{w}}d(x, x_{ℓ_{1}+1})^{p} = max_{j∈{ℓ_{1}+1,...,ℓ_{1}+ℓ_{2}}} ∑_{x∈C_{j}∩T_{w}}d(x, x_{j})^{p}.

Denote

A_{w} = (⋃_{j=1}^{ℓ_{1}} C_{j} )∩ T_{w} and A_{u} = ( ⋃_{j=ℓ_{1}+1}^{ℓ_{1}+ℓ_{2}} C_{j} )∩ T_{u}.

We also write s_{1} = |{y_{1}, …, y_{s}} ∩ T_{u}| + r_{1} and s_{2} = |{y_{1}, …, y_{s}} ∩ T_{w}| + r_{2}, so that s = s_{1} + s_{2} − r_{1} − r_{2}. Note that by definition

∑_{j=1}^{ℓ_{1}} ( ∑_{x∈C_{j}∩T_{u}}d(x, x_{j})^{p})^{1/p} B^{∗}(u, ℓ_{1}, s_{1}, t_{1}),  (38)

and

∑_{j=ℓ_{1}+1}^{ℓ_{1}+ℓ_{2}} ( ∑_{x∈C_{j}∩T_{w}}d(x, x_{j})^{p})^{1/p} B^{∗}(w, ℓ_{2}, s_{2}, t_{2}).  (39)

Thus

B^{∗}(v, ℓ, s, t) = ∑_{j=1}^{ℓ_{1}} [ ∑_{x∈C_{j}∩T_{u}}d(x, x_{j})^{p} + |C_{j} ∩ A_{w}|Δ(v)^{p}]^{1/p} + ∑_{j=ℓ_{1}+1}^{ℓ_{1}+ℓ_{2}} [ ∑_{x∈C_{j}∩T_{w}}d(x, x_{j})^{p} + |C_{j} ∩ A_{u}|Δ(v)^{p}]^{1/p}

B^{∗}(u, ℓ_{1}, s_{1}, t_{1}) + B^{∗}(w, ℓ_{2}, s_{2}, t_{2}) + (t_{1}^{p} + r_{2}Δ(v)^{p})^{1/p} − t_{1} + (t_{2}^{p} + r_{1}Δ(v)^{p})^{1/p} − t_{2}  (40)
B(u, ℓ_{1}, s_{1}, t_{1}) + B(w, ℓ_{2}, s_{2}, t_{2}) + (t_{1}^{p} + r_{2}Δ(v)^{p})^{1/p} − t_{1} + (t_{2}^{p} + r_{1}Δ(v)^{p})^{1/p} − t_{2}  (41)
B(v, ℓ, s, t),  (42)

where in (40) we used Lemma 11 together with (38) and (39), in (41) we used the inductive hypothesis, and in (42) we used the definition of B(·). This completes the proof of Lemma 3.

References

[1] N. Alon, R. Karp, D. Peleg, and D. West, A graph-theoretic game and its application to the k-server problem, SIAM J. Comput. 24 (1995), no. 1.

[2] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit, Local search heuristics for k-median and facility location problems, SIAM J. Comput. 33 (2004), no. 3, 544–562.

[3] Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, 37th Annual Symposium on Foundations of Computer Science (1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 184–193.

[4] , On approximating arbitrary metrics by tree metrics, Proceedings of the 30th Annual ACM Symposium on Theory of Computing, ACM, New York, 1998, pp. 161–168.

[5] Y. Bartal, M. Charikar, and D. Raz, Approximating min-sum k-clustering in metric spaces, Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, pp. 11–20.

[6] Y. Bartal, N. Linial, M. Mendel, and A. Naor, On metric Ramsey-type phenomena, Ann. of Math. (2) 162 (2005), no. 2, 643– 709.

[7] Y. Bartal and M. Mendel, Multi-embedding of metric spaces, SIAM J. Comput. 34 (2004), no. 1, 248–259.

[8] S. G. Bobkov and C. Houdré, Some connections between isoperimetric and Sobolev-type inequalities, Mem. Amer. Math. Soc. 129 (1997), no. 616, viii+111.

[9] M. R. Bridson and A. Haefliger, Metric spaces of non-positive curvature, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 319, Springer-Verlag, Berlin, 1999.

[10] B. Brinkman and M. Charikar, On the impossibility of dimension reduction in l_{1}, J. ACM 52 (2005), no. 5, 766–788).

[11] G. Calinescu, H. Karloff, and Y. Rabani, Approximation algorithms for the 0-extension problem, SIAM J. Comput. 34 (2004/05), no. 2, 358–372.

[12] M. Charikar and S. Guha, Improved combinatorial algorithms for facility location problems, SIAM J. Comput. 34 (2005), no. 4, 803–824.

[13] M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys, A constant-factor approximation algorithm for the k-median problem, J. Comput. System Sci. 65 (2002), no. 1, 129–149.

[14] M. Charikar and R. Panigrahy, Clustering to minimize the sum of cluster diameters, J. Comput. Syst. Sci. 68 (2004), no. 2, 417–441.

[15] G. Cornuéjols, G. L. Nemhauser, and L. A. Wolsey, The uncapacitated facility location problem, Discrete location theory, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 1990, pp. 119–171.

[16] M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng, Lower-stretch spanning trees, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 494–503.

[17] J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the 35th annual ACM Symposium on Theory of Computing, 2003, pp. 448–455.

[18] M. Gromov, Metric structures for Riemannian and non-Riemannian spaces, Progress in Mathematics, vol. 152, Birkhäuser Boston Inc., Boston, MA, 1999. Based on the 1981 French original; With appendices by M. Katz, P. Pansu and S. Semmes. Translated from the French by Sean Michael Bates.

[19] S. Guha and S. Khuller, Greedy strikes back: improved facility location algorithms, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), ACM, New York, 1998, pp. 649–657.

[20] A. Gupta, M. Hajiaghayi, and H. Räcke, Oblivious Network Design, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (Miami, FL, 2006), ACM, New York, 2006, pp. 970–979.

[21] A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair, Cuts, trees and l_{1}-embeddings of graphs, Combinatorica 24 (2004), no. 2, 233–269.

[22] S. Har-Peled and M. Mendel, Fast construction of nets in low dimensional metrics, and their applications, SIAM J. Comput. 35 (2006), no. 5, 1148–1184.

[23] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003), no. 6, 795–824.

[24] K. Jain and V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation, J. ACM 48 (2001), no. 2, 274–296.

[25] K. Jain and V. V. Vazirani, An approximation algorithm for the fault tolerant metric facility location problem, Algorithmica 38 (2004), no. 3, 433–439. Approximation algorithms.

[26] M. R. Korupolu, C. G. Plaxton, and R. Rajaraman, Analysis of a local search heuristic for facility location problems, J. Algorithms 37 (2000), no. 1, 146–188.

[27] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor, Measured descent: A new embedding method for finite metrics, Geom. Funct. Anal. 15 (2005), no. 4, 839–858.

[28] M. Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001.

[29] J. R. Lee and A. Naor, Embedding the diamond graph in L_{p} and dimension reduction in L_{1}, Geom. Funct. Anal. 14 (2004), no. 4, 745–747.

[30] , Extending Lipschitz functions via random metric partitions, Invent. Math. 160 (2005), no. 1, 59–95.

[31] M. Mendel and A. Naor, Euclidean quotients of finite metric spaces, Adv. Math. 189 (2004), no. 2, 451–494.

[32] , Ramsey partitions and proximity data structures, J. European Math. Soc. 9 (2007), no. 2, 253–275, available at

    http://arxiv.org/cs/0511084.

[33] P. B. Mirchandani and R. L. Francis (eds.), Discrete location theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1990. A Wiley-Interscience Publication.

[34] I. Newman and Y. Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Discrete Comput. Geom. 29 (2003), no. 1, 77–81.

[35] Y. Rabinovich and R. Raz, Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete Comput. Geom. 19 (1998), no. 1, 79–94.

[36] D. B. Shmoys, É. Tardos, and K. Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the 29th annual ACM Symposium on Theory of Computing, 1997, pp. 265–274.

[37] C. Swamy and D. B. Shmoys, Fault-tolerant facility location, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2003), ACM, New York, 2003, pp. 735–736.