Approximating finite metrics by distributions over tree metrics Daniel Hsu, CSE 2541 IntroductionWe’d like to approximate arbitrary finite metric spaces (X, ρ) with simpler ones. So far, the approximating(host) metric spaces we’ve considered have been (Y ⊂ Rd, `p) for some small d and p ≥ 1. For many ap-plications (e.g. metric labeling, buy-at-bulk network design, minimum cost communication, group Steinertree, metrical task system), tree metrics are also simple and convenient.Definition 1. A tree metric ρTis the shortest-path metric on a tree T .Problem 1. Given a finite metric (X, ρ), find a tree T ⊇ X such that for all x, y ∈ X:1. (dominance) ρ(x, y) ≤ ρT(x, y), and2. (bounded expansion) ρT(x, y) ≤ α · ρ(x, y).A solution to this problem for some α ≥ 1 reduces a number of optimization problems involving generalfinite metrics (X, ρ) to the same problems restricted to tree metrics, losing an α factor in solution quality.Unfortunately, some spaces require α = Ω(|X|). For example, consider Cn, the cycle on n vertices, withunit length edges. Say we delete a single edge {x, y} so we have a tree T . Then, while ρ(x, y) = 1, wehave ρT(x, y) = n − 1. Actually, α = Ω(|X|) is required of any tree metric (not just spanning tree metrics)for approximating Cn(Rabinovich and Raz, 1998). Instead, we’ll approximate (X, ρ) with a distributionover tree metrics. This is often sufficient to give expected approximation/competitive ratios for the aboveapplications, provided that we can sample from the distribution.Definition 2. A distribution D over a family of tree metrics S α-probabilistically approximates a metric(X, ρ) if:1. every metric in S dominates ρ (so ρ(x, y) ≤ ρT(x, y) for all x, y ∈ X, ρT∈ S), and2. for all x, y ∈ X, EρT∼D[ρT(x, y)] ≤ α · ρ(x, y).Problem 2. Given a finite metric (X, ρ), find distribution D over a family of tree metrics S that α-probabilistically approximates (X, ρ).Exercise 1. Show that Cncan be 2-probabilistically approximated by a distribution over (spanning) treemetrics (Karp, 1989).In this note, we’ll show the construction of Fakcharoenphol, Rao, and Talwar (2003) that achievesα = O(log |X|) for any finite metric (X, ρ), which is optimal up to constant factors (Bartal, 1998). Thus,any finite metric space (X, ρ) embeds into a distribution over dominating tree metric spaces with O(log |X|)distortion. The construction gives an efficient procedure for sampling from this distribution.1.1 OutlineWe’ll show a randomized algorithm that constructs a sequence of decompositions of X, which are of in-terest in their own right. This sequence of decompositions in turn defines a tree T ⊃ X for which ρTdominates ρ. Thus, we’ll have implicitly (algorithmically) described a distribution over tree metrics. Let-ting ρTbe a random variable following this distribution, we’ll prove that E[ρT(x, y)] ≤ ρ(x, y) · O(log |X|).2 The algorithmLet (X, ρ) be the finite metric space with |X| = n and diameter ∆ = maxx,y∈Xρ(x, y). Without loss ofgenerality, we’ll assume that ρ(x, y) > 1 for all x, y ∈ X, x 6= y, and that ∆ = 2δfor some δ ∈ N. For somex ∈ X and r > 0, the ball of radius r centered at x is B(x, r) = {y ∈ X : ρ(x, y) ≤ r}.12.1 From decompositions to treesDefinition 3. An r-cut decomposition of X is a partitioning of X into clusters {S1, S2, . . .} such that eachcluster Si⊆ B(xi, r) for some xi∈ X.Definition 4. A hierarchical cut decomposition of X is a sequence of δ+1 partitionings D0, D1, . . . , Dδsuchthat Dδ= {X} and each Direfines Di+1and is a 2i-cut decomposition of X. Note that because ρ(x, y) > 1for x 6= y, each cluster in D0is a singleton set, i.e. D0= {{x} : x ∈ X}.The following procedure constructs an r-cut decomposition of any S ⊆ X. It will be repeatedly calledto construct a hierarchical cut decomposition of X. Let π be a permutation over the points in X.Procedure Partition(S, π, r):• For j = 1, 2, . . . until S = ∅:• Sj← B(π(j), r) ∩ S.• S ← S \ Sj.• Return {S1, S2, . . .}.A hierarchical cut decomposition naturally arrange in a tree T : let the children of S ∈ Di+1be theS0∈ Dithat partition S (i.e. the S0∈ Di+1with S0⊆ S). So, the δ + 1 levels of the tree are exactlyD0, D1, . . . , Dδwith the singleton sets of D0as the leaves. Let all edges between nodes in Diand Di+1have length 2i+1, so the edge lengths on the path from the root X to any leaf {x} decreases by a factor oftwo in each step.2δ2δ2δ2 2 22δ−12δ−12δ−12δ−12δ−1Sδ−12. . .Sδ−22XSδ−11Sδ−21. . .. . ..........{x1} {x2} {xn}Dδ−1= {Sδ−11, Sδ−12, . . .}Dδ= {X}Dδ−2= {Sδ−21, Sδ−22, . . .}D0= {{x} : x ∈ X}. . .2.2 Distances in TBefore describing the randomized algorithm for decomposing X (it will be repeated invocations of Partition),we first consider the metric ρTinduced by the tree T corresponding to the hierarchical cut decomposition2D0, D1, . . . , Dδ(equate the singleton sets {x} ∈ D0with the respective x ∈ X, so ρTis indeed a metric overX). For any x, y ∈ X, x 6= y, we say the pair (x, y) is at level i if x and y last appear in different clusters inDi, in order of increasing i. Equivalently, (x, y) is at level i if x and y first appear in the same cluster S inDi+1. The path from x to y in T includes the edges leading up from x to this joining cluster S, and thoseleading back down to the leaf y. Thus, the distance ρT(x, y) isρT(x, y) = 21+ 22+ . . . 2i+1|{z }path up the tree+ 2i+1+ 2i+ . . . + 21|{z }path down the tree= 2i+1Xj=12j. (1)Thus 2i+2≤ ρT(x, y) < 2i+3. The metric ρTdominates ρ because each v ∈ S ∈ Di+1is at most distance2i+1from some u ∈ X, so ρ(x, y) ≤ ρ(x, u) + ρ(u, y) ≤ 2 × 2i+1= 2i+2≤ ρT(x, y). The goal is now clear. Wewant to (randomly) construct the decompositions D0, D1, . . . , Dδso that any pair (x, y) with ρ(x, y) ≈ 2iis(in expectation) at level ≈ i.2.3 The main algorithmWe now state the algorithm for decomposing X into the hierarchical cut decomposition D0, D1, . . . , Dδ.First, choose a permutation π of the points in X uniformly at random. Then, independently choose βuniformly at random from the interval [1, 2]. Set Dδ= {X}. Then, for i = δ − 1, δ − 2, . . . , 0, letDi=[S∈Di+1Partition(S, π, 2i−1β). (2)It’s clear from this description that for 0 ≤ i < δ, we have that Diis a 2i-cut decomposition and that Direfines Di+1. The resulting