LAST but not Least: Online Spanners for Buy-at-Bulk
Anupam Gupta∗

R. Ravi†

Kunal Talwar‡

Seeun William Umboh§

arXiv:1611.00052v1 [cs.DS] 31 Oct 2016

November 2, 2016

Abstract
The online (uniform) buy-at-bulk network design problem asks us to design a network,
where the edge-costs exhibit economy-of-scale. Previous approaches to this problem used treeembeddings, giving us randomized algorithms. Moreover, the optimal results with a logarithmic
competitive ratio requires the metric on which the network is being built to be known up-front;
the competitive ratios then depend on the size of this metric (which could be much larger than
the number of terminals that arrive).
We consider the buy-at-bulk problem in the least restrictive model where the metric is
not known in advance, but revealed in parts along with the demand points seeking connectivity
arriving online. For the single sink buy-at-bulk problem, we give a deterministic online algorithm
with competitive ratio that is logarithmic in k, the number of terminals that have arrived,
matching the lower bound known even for the online Steiner tree problem. In the oblivious case
when the buy-at-bulk function used to compute the edge-costs of the network is not known in
advance (but is the same across all edges), we give a deterministic algorithm with competitive
ratio polylogarithmic in k, the number of terminals.
At the heart of our algorithms are optimal constructions for online Light Approximate
Shortest-path Trees (LASTs) and spanners, and their variants. We give constructions that
have optimal trade-offs in terms of cost and stretch. We also define and give constructions for a
new notion of LASTs where the set of roots (in addition to the points) expands over time. We
expect these techniques will find applications in other online network-design problems.

∗
Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. Research partly supported by NSF awards CCF-1319811, CCF-1540541 and CCF-1617790.
†
Tepper School of Business, Carnegie Mellon University, USA, ravi@cmu.edu; This material is based upon research
supported in part by the U. S. Office of Naval Research under award number N00014-12-1-1001, and the U. S. National
Science Foundation under award number CCF-1527032.
‡
Google Research
§
Department of Mathematics and Computer Science, Eindhoven University of Technology, Netherlands. Email:
seeun.umboh@gmail.com. This work was supported in part by ERC consolidator grant 617951 and NSF grant CCF1320854. Part of this work was done while a student at the University of Wisconsin - Madison, and while visiting
the Simons Institute for the Theory of Computing.

Contents
1 Introduction

2

2 Preliminaries

6

3 LASTs

8

4 Multi-Sink LASTs

9

5 Non-Oblivious Buy at Bulk

13

6 Multi-Commodity Spanners

18

7 Randomized Oblivious Buy at Bulk

22

8 Deterministic Oblivious Buy at Bulk

27

9 Conclusions

30

1

1

Introduction

The model of (uniform) buy-at-bulk network design captures economies-of-scale in routing problems. Given an undirected graph G = (V, E) with edge lengths d : E → R≥0 —we can assume the
lengths form a metric—the cost of sending xe flow over any edge e is d(e) · f (xe ) where f is some
concave cost function. The total cost is the sum over all edges of the per-edge cost. Given some
traffic matrix (a.k.a. demand), the goal is now to find a routing for the demand to minimize the
total cost. This model is well studied both in the operations research and approximation algorithms
communities, both in the offline and online settings. In the offline setting, an early result was an
O(log k)-approximation due to Awerbuch and Azar, one of the first uses of tree embeddings in
approximation algorithms [AA97]—here k is the number of demands. For the single-sink case, the
first O(1)-approximation was given by [GMM09]. In fact, one can get a constant-factor even for
the “oblivious” single-sink case where the demands are given, but the actual concave function f is
known only after the network is built [GP12].
The problem is just as interesting in the online context: in the online single-sink problem, new
demand locations (called terminals) are added over time, and these must be connected to the central
root node as they arrive. This captures an increasing demand for telecommunication services as
new customers arrive, and must be connected via access networks to a central core of nodes already
provisioned for high bandwidth. The Awerbuch-Azar approach of embedding G into a tree metric
T with O(log n) expected stretch (say using [FRT04]), and then routing on this tree, gives an
O(log n)-competitive randomized algorithm even in the online case. But this requires that the
metric is known in advance, and the dependence is on n, the number of nodes in the metric, and
not on the number of terminals k! This may be undesirable in situations when n  k; for example,
when the terminals come from a Euclidean space Rd for some large d. Moreover, we only get a
randomized algorithm (competitive against oblivious adversaries).1
In this paper, we study the Buy-at-Bulk problem in the online setting, in the least restrictive model
where the metric is not known in advance, so the distance from some point to the previous points
is revealed only when the point arrives. This forces us to focus on the problem structure, since we
cannot rely on powerful general techniques like tree embeddings. Moreover, we aim for deterministic
algorithms for the problem. Our first main result is an asymptotically optimal deterministic online
algorithm for single-sink buy-at-bulk.
Theorem 1.1 (Deterministic Buy-at-Bulk). There exists a deterministic O(log k)-competitive algorithm for online single-sink buy-at-bulk, where k is the number of terminals.
Note that the guarantee is best possible, since it matches the lower bound [IW91] for the special
case of a single cable type encoding the online Steiner tree problem.
En route, we consider a generalization of the Light Approximate Shortest-path Trees (LASTs).
Given a set of “sources” and a sink, a LAST is a tree of weight close to the minimum spanning tree
(MST) on the sources and the sink, such that the tree distance from any source to the sink is close to
the shortest-path distance. Khuller, Raghavachari, and Young [KRY95] defined and studied LASTs
in the offline setting and showed that one can get constant stretch with cost constant times the
MST. Ever since their work, LASTs have proved very versatile in network design applications. We
1

The tree embeddings of Bartal [Bar96] can indeed be done online with O(log k log ∆) expected stretch, where ∆
is the ratio of maximum to minimum distances in the metric. Essentially, this is because the probabilistic partitions
used to construct the embedding can be computed online. This gives an O(log2 k)-competitive randomized algorithm,
alas sub-optimal by a logarithmic factor, and still randomized.

2

first give (in §3) a simple construction of LASTs in the online setting where terminals arrive online.
We get constant stretch, and cost at most O(log k) times the MST, which is the best possible in
the online case.
For our algorithms, we extend the notion of LASTs to the setting of MLASTs (Multi-sink LASTs)
where both sources and sinks arrive over time. We have to maintain a set of edges so that every
source preserves its distance to the closest sink arriving before it, at minimum total cost. We
provide a tight deterministic online algorithm also for MLASTs, which we think is of independent
interest. This construction appears in §4. Then we use MLASTs to prove Theorem 1.1 in §5.
Oblivious Buy-at-Bulk. We then change our focus to the oblivious problem. Here we are given
neither the terminals nor the buy-at-bulk function f in advance. When the terminals arrive, we have
to choose paths for them to the root, so that for every concave cost function f , the chosen routes
are competitive to the optimal solution for f . Our first result for this problem is the following:
Theorem 1.2 (Oblivious Buy-at-Bulk, Randomized). There exists a randomized online algorithm
for the buy-at-bulk problem that produces a routing P such that for all concave functions f ,


E costf (P ) ≤ O(log2 k) OPTf .
This randomized algorithm has the same approximation guarantee as one obtained using Bartal’s
tree-embedding technique. The benefit of this result, however, is in the ideas behind it. We give
constructions of low-stretch spanners in the online setting. Like LASTs, spanners have been very
widely studied in the offline case; here we show how to maintain light low-stretch spanners in the
online setting (in §6). Then we use the spanners to prove the above theorem in §7. Moreover,
building on these ideas, we give a deterministic algorithm in §8.
Theorem 1.3 (Oblivious Buy-at-Bulk, Deterministic). There exists a deterministic online algorithm for the buy-at-bulk problem that produces a routing P such that for all concave functions
f,
costf (P ) ≤ O(log2.5 k) OPTf .
A question that remains open is whether there is an O(log k)-competitive algorithm for this problem. The only other deterministic oblivious algorithm we know for the buy-at-bulk problem is
a derandomization of the oblivious network design algorithm from [GHR06], which requires the
metric to be given in advance.
LASTs and Spanners. A central contribution of our work is to demonstrate the utility of online
spanners in building networks exploiting economies-of-scale. We record the following two theorems
on maintaining LASTs and spanners in an online setting, since they are of broader interest. These
results are near-optimal, as we discuss in the respective sections.
Theorem 1.4 (Online LAST). There exists a deterministic online algorithm for maintaining a
tree with cost O(log k) times the MST, and a stretch of 7 for distances from terminals to the sink.
Theorem 1.5 (Online Spanner). There exists a deterministic online algorithm that given k pairs
of terminals, maintains a forest with cost O(log k) times the Steiner forest on the pairs, and a
stretch of O(log k) for distances between all given pairs of terminals. Moreover, the total number
of edges in the forest is O(k), i.e. linear in the number of terminals.
Our results on online LAST and multicommodity spanners give us an optimal O(log k)-competitive
deterministic algorithms for the “single cable version” of the buy-at-bulk problems, where the
function is a single-piece affine concave function [MP98].
3

1.1

Our Techniques

We now outline some of the ideas behind our algorithms and the role of spanner constructions in
them. All our algorithms share the same high-level framework: (1) each terminal v is assigned an
integer type τ (v); (2) it is then routed through a sequence of terminals with increasing types; (3)
the routes are chosen using a spanner-type construction. In particular, each algorithm is specified
by a type-selection rule, the sequence of terminals to route through, and whether to use a spanner
or MLAST.
The analysis for our deterministic algorithms also has a common thread: while these algorithms are
not based on tree-embeddings, the analysis uses tree-embeddings crucially. Both analyses are based
on the analysis framework of [Umb15] and follow the same template: we fix an HST embedding T
of the metric, and charge the cost of the algorithm to the cost of the optimal solution on this tree
(losing some factor α). Since HSTs can approximate general metrics to within a factor of O(log k),
this gives us an O(α log k)-competitive algorithm.
Functions vs. Cables. As is common with buy-at-bulk algorithms, we represent the function
f (x) as the minimum of affine functions mini {σi +βi x}. And when we route a path, we even specify
which of the linear functions we use on each edge of this path. Each i is called a “cable type”, since
one can think of putting down cable-i with an up-front cost of σi , and then paying βi for every unit
of flow over it.
Non-oblivious algorithm. In the non-oblivious setting where we know the function f , we will
want to route each terminal v through a path P (v) with non-decreasing cable types. So τ (v) should
simply be the cable of lowest type that we will install on P (v)—how should we choose this value?
It makes sense to choose τ (v) based on the number of other terminals close to v. Intuitively, the
more terminals that are nearby, the larger the flow that can be aggregated at v, making it natural
to select a larger type for v.
Once we have chosen the type, the route selection is straightforward: first we route v’s demand to
the nearest terminal of higher type using cable type τ (v). Then we iterate: while v’s demand is at
a terminal w (which is not the root r), we route it to a terminal w0 of type higher than τ (w) that
nearest to w, using cable type τ (w).
Finally, how do we select the path when routing v’s demand from w to w0 ? This is where our
Multi-sink LAST (MLAST) construction comes in handy. We want that for each cable type i, the
set of edges Hi on which we install cable type i has a small total cost while ensuring that each
terminal of type i has a short path to its nearest terminal of higher type. We can achieve these
properties by having Hi be an MLAST with the sources being the terminals of type exactly i, and
the sinks being terminals of type higher than i.
Randomized Oblivious Algorithm. While designing oblivious algorithms seems like a big
challenge because we have to be simultaneously competitive for all concave cost functions, Goel
and Estrin [GE05] showed that functions of the form gi (x) = min{x, 2i } form a “basis” and hence
we just have to be good against all these so-called “rent-or-buy” functions. This is precisely our
goal.
Note that the optimum solution for the cost function g0 is the optimal Steiner tree, and that for the
cost function gM , for M  k, is the shortest path tree rooted at the sink. Thus being competitive
against g0 and gM already requires us to build a LAST. Thus it is not surprising that our online
spanner algorithm is a crucial ingredient in our algorithm.

4

There are two key ideas. The first is that to approximate a given rent-or-buy function, it suffices
to figure out which terminals should be connected to the root via “buy” edges—i.e., via edges of
cost 2i regardless of the load on them—these terminals we call the “buy” terminals. The rest of the
terminals are simply connected to the buy terminals via shortest paths. One way to choose a good
set of buy terminals is by random sampling: if we wanted to be competitive against function gi ,
we could choose each terminal to be a “buy” terminal with probability 2−i . (See, e.g., [AAB04].)
Since in the oblivious case we don’t know which function gi we are facing, we have to hedge our
bets. Hence we choose each terminal v to have τ (v) = i with probability 2−i . Thus terminal v is a
good buy terminal for all gi with i ≤ τ (v).
Next, we need to ensure that the path P (v) we choose for v simultaneously approximates the
shortest path from v to the set of terminals with type at least i for all i. This is where our online
spanner construction comes in handy. For each type i, we will build a spanner Fi on terminals of
type at least i.
Deterministic Oblivious Algorithm. To obtain our deterministic oblivious algorithm, we
make two further modifications. First, we remove the need for randomness by using the deterministic type selection rule of the non-oblivious algorithm. This modification already yields an
O(log3 k)-competitive algorithm. A technical difficulty that arises is that our type-classes are no
longer nested. Thus it is not obvious how to route from a node of type i to one of a higher type, as
these nodes may not belong to a common spanner. Adding nodes to multiple spanners can remedy
this, but leads to a higher buy cost; being stingy in adding nodes to spanners can lead to higher
rent cost. By carefully balancing these two effects and using a more sophisticated routing scheme,
we are able to improve the competitive ratio to O(log2.5 k).

1.2

Other Related Work

Offline approximation algorithms for the (uniform) buy-at-bulk network design problem were initiated in [SCRS97]—here uniform denotes the fact that all edges have the same cost function
f (·), up to scaling by the length of the edge. Early results for approximation algorithms for
buy-at-bulk network design [MP98, AA97] already observed the relationship to spanners, and
tree embeddings. Using the notion of probabilistic embedding of arbitrary metrics into tree metrics [AKPW95, Bar96, Bar98, Bar04, FRT04], logarithmic factor approximations are readily derived
1
for the buy-at-bulk problem in the offline setting. A hardness result of O(log /4−ε n) shows we cannot do much better in the worst case [And04].
For the offline single-sink case, new techniques were developed to get O(1)-approximations [GMM09],
as well as to prove O(1)-integrality gaps for natural LP formulation [GKK+ 01, Tal02]; other algorithms have been given by [GKR03, GI06, JR09]. Apart from its inherent interest, the single-sink
buy-at-bulk problem can also be used to solve other network design problems [GRS11]. The oblivious single-sink version was first studied in [GE05], and O(1)-approximations for this very general
version was derived in [GP12].
In the setting of online algorithms, the Steiner tree and generalized Steiner forest problems have
tight O(log k)-competitive algorithms [BC97, IW91], where k is the number of terminals. These
algorithms work in the model where new terminals only reveal their distances to previous terminals
when they arrive, and the metric is not known a priori. It is well-known that the tree-embedding
result of Bartal [Bar96] can be implemented online to give an O(log k·min(log ∆, log k))-competitive
algorithm for the online single-sink oblivious buy-at-bulk problem, where ∆ is the ratio of maximum
to minimum distances in the metric. For online rent-or-buy, Awerbuch, Azar, and Bartal [AAB04]

5

gave an O(log2 k)-deterministic and an O(log k)-randomized algorithm; recently, [Umb15] gave an
O(log k)-deterministic algorithm.
If the metric is known a priori, the results depend on n, the size of the metric, and not on k,
the number of terminals.2 E.g., tree-embedding results of [FRT04] give a randomized O(log n)competitive algorithm, or a derandomization of oblivious network design from [GHR06] gives an
O(log2 n)-competitive algorithm.
A generalization which we do not study here is the non-uniform buy-at-bulk problem, where we
can specify a different concave function on each edge. A poly-logarithmic approximation for this
problem was recently given by Ene et al. [ECKP15]; see the references therein for the rich body of
prior work.

2

Preliminaries

Formally, in the online buy-at-bulk problem, we have a complete graph G = (V, E), and edge
lengths d(e) satisfying the triangle inequality. In other words, we can treat (V, d) as a metric. We
have M cable types. The i-th cable type has fixed cost σi and incremental cost βi , with σi > σi−1
and βi < βi−1 . Routing x units of demand through cable type i on some edge e costs (σi + βi x)d(e).
In the single-sink version, we are given a root vertex r ∈ V . Initially, no cables are installed
on any edges. When a terminal v arrives, we install some cables on some edges and choose a
path P (v) on which to route v’s unit demand. (This routing has to be unsplittable, i.e., along a
single path.) We are allowed to install multiple cables on the same edge; if e ∈ P (v) has multiple
cables installed on it, v’s demand is routed on the one with highest type, i.e., the one with least
incremental cost. The choice of P (v) and cable installations are irrevocable. Given a routing
solution,
demand routedP
through
i (e) is the total amount of 
P
P cable type i on edge e, the total
Pif load
cost is e∈E
i:load
P i (e)>0
P σi + βi loadi (e) d(e). We call e∈E i:loadi (e)>0 σi d(e) the fixed cost of
the solution and e∈E i:loadi (e)>0 βi loadi (e)d(e) the incremental cost of the solution. Let OPT
denote the cost of the optimal solution. We assume the cable costs satisfy the conditions of the
following Lemma 2.1.
Lemma 2.1. [GMM09] We can prune the set of cables such that for all the retained cable types
i, (a) σi ≥ 3σi−1 , and (b) βi ≤ (1/32 )βi−1 , so that the cost of any solution using only the pruned
cable types increases only by an O(1) factor.

2.1

HST embeddings

Let (X, d) be a metric over a set of points X with distances d at least 1.
Definition 2.2 (HST embeddings [Bar96]). A hierarchically separated tree (HST) embedding T of
metric (X, d) is a rooted tree with height dlog2 (maxu,v∈X d(u, v))e and edge lengths that are powers
of 2 satisfying:
a. The leaves of T are exactly X.
b. The length of the edge from any node to each of its children is the same.
c. The edge lengths decrease by a factor of 2 as one moves along any root-to-leaf path.
For e ∈ T , we use T (e) to denote the length of e and say that e is a level-j edge if T (e) = 2j .
Furthermore, we write T (u, v) to denote the distance between u and v in T . We also use L(e)
2

Note that k is at most n, and it can be much smaller.

6

denote the leaves that are “downstream” of e, i.e. they are the leaves that are separated from the
root of T when e is removed from T .
The crucial property of HST embeddings that we will exploit in our analyses is the following
proposition, which follows directly from Properties (2) and (3) of Definition 2.2.
Proposition 2.3. Let T be a HST embedding T of (X, d). For any level-j edge e ∈ T , we have
d(u, v) < 2j for any u, v ∈ L(e).
Corollary 2.4 ([AA97, FRT04]). For any online buy-at-bulk instance with k terminals X and
distances d, there exists a HST embedding T of (X, d) such that OPT(T ) ≤ O(log k) OPT, where
OPT(T ) is the cost of the optimal solution for online buy-at-bulk with terminals X in the tree T .

2.2

Decomposition into rent-or-buy instances

Since buy-at-bulk functions can be complicated, it will be useful to deal with simpler rent-or-buy
functions where to route a load of x on an edge, we can either buy the cable for unlimited use at
its buy cost, or pay the rental cost times the amount x. Given a buy-at-bulk instance as above, for
each i, define the rent-or-buy instance with the rent-or-buy function fi (x) = min{σi , βi−1 x}. Let
OPTi to be the cost of the optimum solution with respect to this function fi . Note that under this
i
function when the load aggregates up to βσi−1
, it becomes advantageous to switch from renting to
buying.
The following lemma will prove very useful, since we can charge different parts of our cost to different
OPTi (T )s for some HST T , and then sum them up to argue that the total cost is O(1) OPT(T ),
and hence O(log k) OPT using Corollary 2.4.
P
Lemma 2.5 (OPT Decomposition on Trees). For every tree T , we have i OPTi (T ) ≤ O(1) OPT(T ).
Proof. For an edge e ∈ T , let φ∗i (e) and φ∗ (e) be the costs incurred
P by OPTi (T ), and OPT(T )
respectively, on e. We will show that for every edge e ∈ T , we have i φ∗i (e) ≤ O(1)φ∗ (e). Let X(e)
be the set of terminal-pairs whose tree paths (in the single-sink case, terminals whose paths to r) in
T include e, and T (e) denote the length of the tree edge e. So, φ∗i (e) = T (e) · min{σi , βi−1 |X(e)|}
and φ∗ (e) = T (e) · mini {σi + βi |X(e)|}. For any fixed j, we have
X
X
X
min{σi , βi−1 |X(e)|} ≤
σi +
βi−1 |X(e)|
i

i≤j

i>j

≤ O(1)(σj + βj |X(e)|),
where the last inequality follows from the fact that the fixed costs σi increase geometrically with i
and the incremental costs βi decrease geometrically with i, as assumed in Lemma 2.1.
P
P
Thus, i φ∗i (e) ≤ O(1)φ∗ (e) for every edge e ∈ T and so i OPTi (T ) ≤ O(1) OPT(T ).
The next lemma proves that the rent-or-buy functions form a “basis” for buy-at-bulk functions.
For i ∈ Z≥0 , define the rent-or-buy function gi (x) = min{x, 2i }. (See, e.g., [GP12, Section 2].)
Lemma 2.6 (Basis of Rent-or-Buy Functions). Fix some routing of demands. If for every i, the
cost of this routing under gi is within a factor of ρ of the optimal routing for gi , then for any
monotone, concave function f with f (0) = 0, the cost of the routing under f is within O(ρ) of the
optimal cost of routing under f .

7

3

LASTs

In the light approximate shortest-path tree (LAST) problem, we are given a graph G = (V, E)
with edge costs d(u, v) and a root r, and we seek a low-cost spanning subtree T that preserves
distances to the root. Let MST denote the cost of the minimum spanning tree. We say that T is
an (α, β)-LAST if c(T ) ≤ α MST and dT (v, r) ≤ β d(v, r) for all v ∈ V . Without loss of generality,
G is complete and d is a metric on V . In the online setting, terminals arrive one by one; when a
terminal arrives, its distances to previous terminals are revealed and the algorithm picks an edge
that connects the new terminal to a previous one. We prove the following theorem.
Theorem 1.4 (Online LAST). There exists a deterministic online algorithm for maintaining a
tree with cost O(log k) times the MST, and a stretch of 7 for distances from terminals to the sink.
High-level overview. Our algorithm maintains a greedy online Steiner tree T plus a set of edges
A which we call the “direct” edges. The subgraph H produced by the graph consists of a subset
of edges from T ∪ A. When terminal v arrives, the algorithm considers the shortest (v, r)-path Pv
contained in T ∪ A; if d(Pv ) > 7d(v, r), then it adds (v, r) to H and A, otherwise it adds Pv to H.
The formal algorithm is presented as Algorithm 1.
Algorithm 1 Online LAST
1:
2:
3:
4:
5:
6:
7:
8:
9:

3.1

T ← ∅; H ← ∅; A ← ∅
while terminal v arrives do
Let u be closest previous terminal
Add (u, v) to T
Let Pv be the shortest (v, r)-path in T ∪ A
if d(Pv ) > 7d(v, r) then
Add (v, r) to H and A
else
Add Pv to H

Analysis

Since H ⊆ T ∪ A and c(T ) ≤ O(log n) MST, it suffices to bound c(A).
Lemma 3.1. c(A) ≤ 2c(T ).
P
P
Proof. Define Z = {v : (v, r) ∈ A}. Note that c(A) = e∈A d(e) = v∈Z d(v, r). For each v ∈ Z,
define Lv to be the segment of the (v, r)-path in T that is contained in a ball centered at v of radius
d(v, r)/2. The lemma follows if we can show that these segments are disjoint. The following claim
implies that they are disjoint.
Claim 3.2. For every v, v 0 ∈ Z, we have dT (v, v 0 ) > d(v, r)/2 + d(v 0 , r)/2.
Proof. Suppose, towards a contradiction, that for some v, v 0 ∈ Z, we have dT (v, v 0 ) ≤ d(v, r)/2 +
d(v 0 , r)/2 and v arrived after v 0 . Consider the point in time when the v arrived. Since (v 0 , r) ∈ A,
a possible (v, r)-path in T ∪ A, is to take the (v, v 0 )-path in T followed by (v 0 , r). So
d(Pv ) ≤ dT (v, v 0 ) + d(v 0 , r) ≤

d(v, r) d(v 0 , r)
+
+ d(v 0 , r).
2
2

Furthermore, v ∈ Z implies d(Pv ) > 7d(v, r). Therefore, d(v, r) < d(v 0 , r)/4.
8

On the other hand,
d(v 0 , r) ≤ d(v 0 , v) + d(v, r)
≤ dT (v 0 , v) + d(v, r)
d(v, r) d(v 0 , r)
+
+ d(v, r)
2
2
d(v 0 , r) d(v 0 , r) d(v 0 , r)
<
+
+
8
2
4
0
< d(v , r).
≤

This gives the desired contradiction.
Therefore, the segments Lv are disjoint, so c(A) = 2

4

P

v∈Z

|Lv | ≤ 2c(T ).

Multi-Sink LASTs

Recall that LASTs were Light Approximate-Shortest-path Trees, i.e., trees where we maintain the
shortest-path distance of sources to a sink, using a light tree. (This was traditionally done offline,
but in §3 we show how to maintain this online—though the reader is not required to know the
offline construction for this section.) In this section, we are interested in the multi-sink LAST
(MLAST) problem. The input is a sequence of terminals in the underlying metric G, each of which
is either a source or a sink (we assume the first terminal is always a sink), and our algorithm has
to maintain a subgraph H such that (a) the distance of any source to its closest sink in H should
be comparable to the distance of that source to its closest sink in G, and moreover (b) the cost
d(H) should not be “too large”.
Note that when a new sink s arrives, it may be close to many sources, and hence we may need to
add “shortcut” edges to reduce their distance to s. Moreover, what does it mean for the cost of H
to not be “too large”, since the distance from a source to its closest sink can fall dramatically over
time. Our notion is the following. Note that when a source v arrives, it has to pay at least the
distance to its closest terminal (source or sink) at that time, just to maintain connectivity. Loosely,
we want our cost d(H) to be not much more than the sum of these distances. (N.b.: this is the
intuition, formally we will pay O(2class(v) ) which will be defined soon.)

4.1

The Algorithm

The first terminal to arrive is a sink we denote as s? . We use R and S to denote the sets of sources
and sinks that have arrived. For a terminal u, let R(u) and S(u) be the sources and sinks that
arrived strictly before u. Our algorithm Mlast-Alg maintains a subgraph H that consists of two
parts: a forest F which is a “backbone” connecting each source to some sink cheaply, and an edge
set A which “augments” F to ensure that each source is not too far from the sinks in H = A ∪ F .
The forest F is constructed using nets which we define now. Let ∆ > 0 be some distance scale.
Then, a ∆-net Z is a subset of terminals (called net points) such that every terminal v has d(v, Z) <
∆ and for every pair of net points u, v ∈ Z, we have d(u, v) ≥ ∆. Initially, both F and A are empty.
The algorithm maintains a 2j -net Zj on the entire set of terminals, for each distance scale j ∈ Z.
When a terminal v arrives, for every distance scale j, it is added to Zj if d(u, Zj ) ≥ 2j . The class
of v is defined to be class(v) := max{j : v ∈ Zj }, i.e., class(v) is the largest distance scale such that
v belongs to the net of that scale. Hence the class of the first terminal s? is ∞.

9

S
Let u be the nearest terminal in j:j>class(v) Zj , i.e., u is the nearest net-point lying in any net at
a higher scale. If the current vertex v is a source, then the edge (u, v) is added to F ; otherwise,
F is left untouched. Next, the algorithm goes through every source u (including v if it is also a
source), checks if dA∪F (u, S) ≤ 3d(u, S), and otherwise adds the edge (u, u0 ) to A where u0 ∈ S is
the nearest sink to u. (See Algorithm 2.)
Algorithm 2 Mlast-Alg(R, S)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

Zj ← ∅ for all j, A ← ∅, F ← ∅, ∆ = 0;
while terminal v arrives do
If d(v, S(v)) > ∆, set diameter ∆ ← d(v, S(v))
for all j ∈ Z do
if d(v, Zj ) ≥ 2j then
Add v to Zj
class(v) ← max{j : v ∈ Zj }
if v ∈ R then
Add edge (u, v) to F where u is a terminal of higher class nearest to v
for x ∈ R do
if dA∪F (x, S) > 3d(x, S) then
Add (x, x0 ) to A where x0 is the terminal in S nearest to u

High-Level Idea of the Analysis. We first state the main properties of our MLAST algorithm
that we will use in the remainder of the paper.
Lemma 4.1. Given an online sequence of sources R and sinks S, the algorithm Mlast-Alg
maintains a subgraph H and assigns classes to terminals such that
P
a. d(H) ≤ O(1) v∈R 2class(v) ,
b. dH (u, S) ≤ 3d(u, S) for every u ∈ R,
c. if class(u) = class(v) = j, then d(u, v) ≥ 2j ,
d. d(u, R(u) ∪ S(u)) ≤ 2class(u) ≤ d(u, s? ) for every u ∈ R, where s? is the first terminal that
arrived, and R(u) and S(u) are the sources and sinks that arrived before u.
Property (a) is the formal bound on the cost of the MLAST. One should think of 2class(v) as being
the radius of some “dual” ball around source v, that we will later use to give lower bounds on
our buy-at-bulk instances. Property (b) guarantees distance preservation. Properties (c) and (d)
ensure that terminals of the same class are well-separated, and that class(u) is not too large. Out
of these, property (a) is the most non-trivial one to prove. The cost of F is easy to bound, since
each source v adds in a single edge of length at most O(2class(v) ). For the cost of edges in A, the
argument at a high level is that the sources adding two different edges of the same length must be
far from each other in H (compared to the length of the edges added) else the later one could use
a path to the earlier one, and then the added edge, to fulfill the distance guarantee.

4.2

Analysis of Mlast-Alg

We devote the remainder of this section to proving Lemma 4.1. First, note that by construction,
Mlast-Alg ensures a short path in H from each source x ∈ R to the sinks S: dH (x, S(x)) ≤
3d(x, S(x)). Secondly, two terminals u and v having the same class j must both belong to the
2j -net Zj so their distance d(u, v) ≥ 2j . Thus, we have proved Properties (b) and (c).
Next, we prove Property (d).
10

u

u’

κ(v)+1

≤2
v

Figure 1: An example tree of F. The hollow vertex at the top is the leader and a sink, and the other
are terminals. When v arrived, the algorithm added the edge (u, v), making v a child of u, and the
length of the edge is at most 2class(v)+1 . Note that it is possible for two terminals u and u0 to have
the same class, and yet u’s children have much larger class than u0 ’s.
Proof of Lemma 4.1 (d). Let class(u) = j. Since every terminal that arrived before u is at distance
d(u, R(u) ∪ S(u)) from u, we have that u belongs to the net Zj − where j − = blog d(u, R(u) ∪ S(u))c.
Thus, 2j ≥ d(u, R(u) ∪ S(u))/2. On the other hand, s? belongs to every net since it was the first
terminal to arrive. Thus, u cannot belong to any net Zj 0 where j 0 > blog d(u, s? )c.
To prove Property (a), we start with some useful properties of the forest F that will allow us to
relate d(H) to the classes of sources. Root each tree T in F using the terminal of highest class in
that tree, which we call the leader of T .
Claim 4.2. Each tree T of the forest F satisfies the following properties:
1. Its leader is a sink and all other terminals are sources.
2. On every leaf-to-leader path of T , the classes of terminals on that path strictly increase.
3. If v ∈ T is a source, then when it arrived, the edge (u, v) was added to F , where u is a
terminal in T with class(u) > class(v) and d(u, v) ≤ 2class(v)+1 .
4. If u is the parent of v and v is an ancestor of t in T , then the length of the (t, u)-path P in
T is dT (t, u) ≤ 2class(v)+2 ≤ 2class(u)+1 .
See Figure 1 for an illustration of properties (1), (2), and (3); and Figure 2 for property (4).
Proof. Properties (1) and (2) follow from the fact that each source has a single edge in T to a
terminal of higher class, and sinks are not connected to other terminals when they arrive.
We now prove property (3). Let (u, v) be the edge added when v arrived. The algorithm
chose
S
u to be the nearest terminal of some higher class. By definition, all terminals in j:j>class(v) Zj
have class at least class(v) + 1. Moreover, the closest net-point to v in Zclass(v)+1 is within distance
2class(v)+1 , so u can be no further. Hence, we have d(v, u) ≤ d(v, Zclass(v)+1 ) ≤ 2class(v)+1 .
Finally, we prove property (4). Suppose u is the parent of v and v is an ancestor of t in the tree
T , and let P be the path in T from t to u. Property (2) implies that the classes of terminals in P
are strictly increasing
P as we move from t to u. Property (3) now implies that the length of the t-u
path P is at most x∈P :x6=u 2class(x)+1 < 2class(v)+2 ≤ 2class(u)+1 . This concludes the proof of the
claim.
Since each edge in F is added by a distinct source, the total cost of F (using Claim 4.2(3)) is:
X
d(F ) ≤ 2
2class(v) .
(1)
v∈R

11

u
≤ 2κ(v)+1

v
v’

t

≤ 2κ(v’)+1

≤ 2κ(t)+1

Figure 2: An illustration of the proof of property (4). Since class(t) < class(v 0 ) < class(v) < class(u)
by properties (2) and (3), the length of the path from t to u is at most 2class(v)+2 ≤ 2class(u)+1 .
It remains to bound d(A) in terms of the classes of sources. The following claim allows us to find
sources to charge d(A) to. Define Aj = {(u, v) ∈ A : d(u, v) ∈ [2j , 2j+1 )}. Observe that every edge
(u, v) ∈ A has one endpoint being a source terminal and another being a sink terminal.
Claim 4.3. Suppose (u, v) ∈ Aj with u being the source endpoint and T is the tree in F containing
u. Then there exists an ancestor ϕ(u) = z of u in T such that z is a source, has class class(z) ≥ j−2,
and the length of the (u, z)-path in T is dT (u, z) ≤ 2j−1 .
Proof. Let a be the sink that is the leader of T . By definition of the algorithm, v is the nearest
sink to u at the moment that (u, v) was added to A, so d(u, v) ≤ d(u, a) ≤ dT (u, a) ≤ 2class(a)+1 ,
where the last inequality follows from Claim 4.2(4). Since (u, v) belongs to Aj , we also have
d(u, v) ≥ 2j . Putting the previous two inequalities together, 2j ≤ 2class(a)+1 and so the leader a has
class(a) ≥ j − 1.
If u has class(u) ≥ j − 2 we are done, so assume class(u) ≤ j − 3. Let t be the highest ancestor
of u such that class(t) ≤ j − 3 (clearly u is a candidate). Observe that t 6= a. Let z be t’s parent;
we claim z satisfies the desired conditions. It has class ≥ j − 2 (by the maximality of t), and
d(u, z) ≤ 2class(t)+2 ≤ 2j−1 by Claim 4.2(4). But we’d already observed that d(u, a) ≥ 2j , so z 6= a;
hence z is a source by Claim 4.2(1).
Proof of Lemma 4.1 (a). To upper bound d(A), we charge the length of each edge (u, v) ∈ A to
a source vertex, and then show that the charge received by each source z is at most O(1)2class(z) .
For each edge (u, v) ∈ A, the charging scheme is defined as follows: if (u, v) ∈ Aj (i.e. its length
d(u, v) ∈ [2j , 2j+1 )) and u is the source endpoint and contained in the tree T of F , charge 2j+1 ≥
d(u, v) to the ancestor ϕ(u) given by Claim 4.3. Hence d(A) is at most the total charge received
by all the sources.
Next, we show that the charge received by every source z is at most O(1)2class(z) . Terminal z is
only charged by edges belonging to Aj for j ≤ class(z) + 2; each such edge charges z charges 2j+1 .
We claim that for
one edge in Aj charges z: P
this means the total charge received
Peach j, at most
j+1
class(z)
by z is at most j≤class(z)+2 2
≤ O(1)2
, so d(A) ≤ z∈R O(1)2class(z) , which proves the
lemma.
To prove the claim, suppose that there exist two edges (u, v), (u0 , v 0 ) ∈ Aj that charge z. Let u
and u0 be sources, and v and v 0 be sinks. Since both edges charge z, ϕ(u) = ϕ(u0 ) = z. Since both
edges belong to Aj , their lengths must satisfy
2j ≤ d(u, v) ≤ 2d(u0 , v 0 ).

12

(2)

z
≤ 2j-1

≤ 2j-1

u’

u

v

Figure 3: An illustration of the situation when two edges (u, v) and (u0 , v 0 ) in Aj charge the same
terminal z, and u and u0 are the source endpoints. The dashed edges represent paths from u0 to z
and u to z in T . There is a path in H from u0 to S following the paths in T represented by the
dashed edges and the edge (u, v).
By definition of the charging scheme,
dT (u0 , z) ≤ 2j−1

and

dT (u, z) ≤ 2j−1 .

(3)

Suppose (u0 , v 0 ) was added to A after (u, v). At the time when we consider adding (u0 , v 0 ), the sink
v ∈ S(u0 ) and so dH (u0 , S) ≤ dH (u0 , v). Moreover, there is a path in H from u0 to v: the path in T
from u0 to u, followed by the edge (u, v), which implies
dH (u0 , S) ≤ dT (u0 , z) + dT (z, u) + d(u, v).
(See Figure 3 for an illustration.) Plugging in the inequalities (2) and (3), we get that dH (u0 , S) ≤
2j + 2d(u0 , v 0 ) ≤ 3d(u0 , v 0 ), where the last inequality follows from the fact that 2j ≤ d(u0 , v 0 ).
However, this contradicts the condition for adding (u0 , v 0 ) to A. Hence only one edge in Aj can
charge any z; this proves the claim and hence the lemma.

5

Non-Oblivious Buy at Bulk

In this section we prove our main result for online buy-at-bulk for the case when the function f is
known.
Theorem 1.1 (Deterministic Buy-at-Bulk). There exists a deterministic O(log k)-competitive algorithm for online single-sink buy-at-bulk, where k is the number of terminals.
For a high-level intuition behind the algorithm, see the discussion in §1.1. Here we explain precisely
how to assign types, update layers and route demands.
Type assignment. Consider a terminal v. At the time of its arrival, for each type i, let di (v) be
the distance to the nearest type-i terminal, and define the ball Bi (v) := {u : d(u, v) ≤ di (v)/23 }.
Let ni (v) := |Bi (v)| be the number of terminals in this ball. Terminal v is assigned type

i
.
τ (v) := max i : ni (v) ≥ βσi−1
To make sense of this, observe that the threshold for being of a certain type is the same as the
threshold for the load at which it is advantageous to buy rather than rent for that type. This
means vertices assigned a certain type can collect enough “witnesses” whose paths to the root in
the optimal solution can be used to pay for edges constructed by v in the online solution.

13

Layers. Let Ri be the current set of terminals of type exactly i, and Xi := ∪i0 ≥i Ri0 be the current
set of terminals of type at least i. Let Xi (v) (resp., Ri (v)) be the set of terminals of type at least
(resp., exactly) i that arrived strictly before v. Layer Hi is maintained by running the online
algorithm Mlast-Alg with Ri as sources and Xi+1 as sinks. This ensures that every u ∈ Ri has
dHi (u, Xi+1 (v)) ≤ 3d(u, Xi+1 (v)).
Routing. We route v’s demand to the root on path P (v) that is constructed as follows. The path
P (v) is constructed iteratively and consists of M different segments Pi (v), one per type. Initially,
v’s demand is located at v and the segments are all empty. While the current terminal w containing
v’s demand is not the root, choose w0 to be the terminal in Hτ (w) with τ (w0 ) > τ (w) nearest to
w (nearest in terms of distances in Hτ (w) ) and route v’s demand to w0 along the shortest path
between w and w0 in Hτ (w) .
This completes the description of the algorithm. See Algorithm 3 for a summary.
Algorithm 3 Online Algorithm for Single-Sink Buy-at-Bulk
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

5.1

τ (r) ← ∞
Hi ← ∅ for all i
while terminal v arrives do
// Determine type of v
Let di (v) = d(v, Xi ), Bi (v) = {u : d(u, v) ≤ di (v)/23 }, and ni (v) = |Bi (v)| for 1 ≤ i ≤ M
i
τ (v) ← max{i : ni (v) ≥ βσi−1
}
// Update layers Hi
for i ≤ τ (v) do
Update Hi using Mlast-Alg with Ri (v) as sources and Xi+1 (v) as sinks
Install cable of type i on new edges of Hi
// Find routing path P (v) to route v’s demand to the root
Pi (v) ← ∅ for all i; P (v) ← ∅
while v’s demand is not yet at r do
Let w be the terminal containing v’s demand and i = τ (w)
Let Pi (v) ⊆ Hi be the shortest path from w to Xi+1 (v) in Hi
Route v’s demand from w to Xi+1 (v) along the path Pi (v)

Analysis

Let us now consider the cost of the algorithm’s solution due to each cable type. The fixed cost
due to cables of type i is σi d(Hi ) since they are installed on layer Hi . For each terminal v of type
τ (v) ≤ i, Pi (v) is the segment of its routing path consisting of type i cables. Hence the total cost
of the algorithm’s solution is

X
X
ALG :=
σi d(Hi ) +
βi d(Pi (v)) .
(4)
i

v:τ (v)≤i

Proof outline. We want to show that ALG ≤ OPT(T ) for any HST embedding T , since Corollary 2.4 would then imply that ALG ≤ O(log k) OPT. The key is to decompose OPT on trees as
follows: in §2.2 we defined the rent-or-buy functions fi (x) := min{σi , βi−1 }, and defined OPTi to
be the cost of the optimal solution with respect to fi . Our proof (specifically Lemmas 5.3 and 5.2)

14

will use the structure of the HST to give a charging argument showing that
X
βi−1 di (v) ≤ O(1) OPTi (T ).
σi d(Hi ) +

(5)

v:τ (v)<i

Roughly speaking, we argue that d(Hi ) can be charged to the optimal cost of the witnesses of the
terminals of type exactly i, and moreover, the type selection rule forces terminals of type less than
i to be spread out.
Thus, if we could prove that d(Pi (v)) ≤ O(1)di+1 (v), then we would be done, because we could
decompose the expression for ALG in (4) as follows:

X
X
βi−1 di (v) .
(6)
σi d(Hi ) +
ALG ≤ O(1) ·
i

v:τ (v)<i

Inequality (5) and Lemma 2.5 would imply that ALG ≤ O(1) OPT(T ) for any HST embedding T ,
as desired.
However, d(Pi (v)) can be much larger than di+1 (v). This is because of the “selfishness” of the
routing scheme: when a terminal w receives v’s demand, it simply routes it to the terminal w0 of
higher type nearest to w, without any regard as to how far w0 is from v. Fortunately, the fact that the
incremental costs βi are geometrically decreasing allows us to show that the P
total incremental cost
incurred
over
all
segments
P
(v)
are
bounded.
In
particular,
we
show
that
i
v:τ (v)≤i βi d(Pi (v)) ≤
P P
O(1) i v:τ (v)≤i βi di+1 (v). The rest of the proof will follow this general outline.
Bounding incremental cost. We begin by proving the above bound on the incremental cost.
P P
P P
Lemma 5.1. The incremental cost i v:τ (v)≤i βi d(Pi (v)) ≤ O(1) i v:τ (v)≤i βi di+1 (v).
Proof. For terminal v, suppose its type-i segment Pi (v) is non-empty: let wi be the starting terminal
of the segment. Since Pi (v) starts with a terminal of type i and ends with a terminal of type at least
i+1, so τ (wi ) = i. Now since Pi (v) is a shortest path in Hi from wi to Xi+1 (v), Lemma 4.1(b) gives
us d(Pi (v)) ≤ 3 · d(wi , Xi+1 (v)). Since di+1 (v) is the distance from v to Xi+1 (v), d(wi , Xi+1 (v)) ≤
0
0
d(w

P i , v) + di+1 (v). Moreover, the segments Pi (v) for i < i form a path from v to w
Pi , so d(wi , v) ≤
0
we get d(Pi (v)) ≤ 3 di+1 (v) + i0 <i d(Pi0 (v)) .
i0 <i d(Pi (v)). Combining these inequalities,P
0
Unrolling the recursion, this gives d(Pi (v)) ≤ i0 ≤i 3i−i +1 di0 +1 (v). Hence, we get the following
bound on the incremental cost of v:
X
X
X
X
X 0
0
βi · d(Pi (v)) ≤
βi ·
3i−i +1 di0 +1 (v) =
di+1 (v) ·
3i −i+1 βi0 ,
i≥τ (v)

i≥τ (v)

i0 ≤i

i≥τ (v)

i0 ≥i

where the equality follows from rearranging the sums. But the βi s decrease geometrically by a
factor of 32 , so the last sum is dominated by the first term, and is O(βi ). Hence the proof.
P
Lemma 5.1 implies Inequality (6). Define ALGi = σi d(Hi ) + v:τ (v)<i βi−1 di (v). The rest of this
section will show that on any HST embedding T , ALGi ≤ O(1) OPTi (T ) for every i. Lemma 2.5
then implies that ALG ≤ O(1) OPT(T ) for any HST embedding T and so ALG ≤ O(log k) OPT
by Corollary 2.4.

15

Charging to HST embeddings. For the following, fix an HST embedding T . Recall that for
edge e ∈ T , L(e) denotes the leaves below e, T (e) the length of e, and T (u, v) the distance between
u and v in T . Also, observe that an edge e such that r ∈
/ L(e), the terminals in L(e) either have
to buy the edge at cost σi T (e), or rent it at cost βi−1 |L(e)|T (e). We record this lower bound for
later.
X
T (e) min{σi , βi−1 |L(e)|}.
(7)
OPTi (T ) ≥
e∈T :r∈L(e)
/

P
To upper-bound ALGi , we bound both σi d(Hi ) and v:τ (v)<i βi−1 di (v) separately by OPTi (T ). In
each case, we proceed by developing an appropriate charging scheme that charges to the edges of
T and then arguing that the total charge received by each edge e ∈ T is at most a constant times
its contribution to the lower bound of OPTi (T ) in Inequality 7.
P
First, we bound v:τ (v)<i βi−1 di (v). The charging scheme is as follows: for each terminal v, charge
βi−1 to an edge in T whose length is proportional to di (v) and which contains v as a leaf. Then
we argue that no edge is overcharged; in particular, for every edge e ∈ T , the total number of
terminals that can charge e is at most σi /βi−1 . Finally, we use the fact that terminals charging
to e are close together (by the bounded diameter property of HSTs), so if there were more than
σi /βi−1 terminals charging e, then the one that arrived last would have been assigned a type of at
least i.
P
Lemma 5.2.
v:τ (v)<i βi−1 di (v) ≤ O(1) OPTi (T ).
Proof. Consider the following charging scheme. For each terminal v with type τ (v) < i, if di (v) ∈
[2j , 2j+1 ), charge 2j+1 βi−1 to the length 2j−4 edge e ∈ T whose leaves L(e) contain v but not r.
j
Such an edge must exist
P since otherwise di (v) ≤ d(v, r) < 2 . The total charge received by the
edges of T is at least v:τ (v)<i βi−1 di (v), and only edges e with r ∈
/ L(e) were charged.
Consider an edge e ∈ T of length 2j−4 . Let C(e) ⊆ L(e) be the set of terminals charging e. We
claim that |C(e)| ≤ σi /βi−1 . Note that the total charge received by e is
2j+1 βi−1 |C(e)| = 25 T (e)βi−1 |C(e)| ≤ 25 T (e) min{σi , βi−1 |L(e)|}.
By (7), this proves the lemma.
Now to prove the claim. Suppose for a contradiction, that |C(e)| > σi /βi−1 . Let v be the lastarriving terminal of C(e). Since e is a length 2j−4 edge and v charged e, we have di (v) ≥ 2j
and τ (v) < i. Moreover, since C(e) ⊆ L(e), we have that diam(C(e)) < 2j−3 ≤ di (v)/23 . Thus,
every terminal u ∈ C(e) is within distance di (v)/23 from v so C(e) ⊆ Bi (v). This implies that
|Bi (v)| ≥ |C(e)| ≥ σi /βi−1 so v should have been assigned a type that is at least i, contradicting
the fact that τ (v) < i. Therefore, |C(e)| ≤ σi /βi−1 , as desired.
Bounding the Fixed Cost of Hi . There are three steps to the proof. The first step is to use
Lemma 4.1 to charge the fixed cost to the terminals of type i. The second is to argue that since
each terminal v of type i has at least σi /βi−1 witnesses nearby, v can use the cost incurred by
OPTi (T ) in routing its witnesses to pay off the charge it accumulated. Finally, we use the fact that
terminals of type i that accumulate similar charges must be far apart to argue that no witness is
overcharged.
Lemma 5.3. σi d(Hi ) ≤ O(1) OPTi (T ).
Proof. The layer Hi is an MLAST whose set of sources is Ri (the terminals of type exactly i)
and sinks Si = Xi+1 , the terminals of higher type. Let classi (v) be the class assigned by this
16

P
MLAST algorithm to terminal v. By Lemma 4.1, we have σi d(Hi ) ≤ O(1) v∈Ri σi 2classi (v) . Define
Ri (j) = {v ∈ Ri : classi (v) = j}. Let Ej be the set of length 2j−4 edges of T . To prove the lemma,
we will show that for each j,
X
min{σi , βi−1 |L(e)|}.
(8)
σi |Ri (j)| ≤
e∈Ej :r∈L(e)
/

This would then imply that
X
X
X
σi d(Hi ) ≤ O(1)
σi 2classi (v) ≤ O(1)
2j σi |Ri (j)| ≤ O(1)
2j−4
v∈Ri

j

j

X

min{σi , βi−1 |L(e)|}.

e∈Ej :r∈L(e)
/

But T (e) = 2j−4 for edges e ∈ Ej , so (7) bounds the cost by O(1) OPTi (T ) to complete the proof.
Now to prove (8). We will show that for each v ∈ Ri (j) (i.e., having type i, and class j in the
MLAST Hi corresponding to type-i terminals), every terminal u in its ball Bi (v) has to be routed
on some level-j edge e ∈ Ej with r ∈
/ L(e), and that the level-j edges used by Bi (v) is disjoint from
the edges used by Bi (v 0 ) for any other v 0 ∈ Ri (j). More formally, for each terminal v, define ej (v)
to be the unique edge of Ej such that v ∈ L(ej (v)) and define Ej (v) := {ej (u) : u ∈ Bi (v)}. We
need the following claims.
Claim 5.4. For every v ∈ Ri (j) and u ∈ Bi (v), we have d(u, v) ≤ 2j−3 .
Proof. By definition of Bi (v), we have the following bound: d(u, v) ≤ di (v)/23 = d(v, Xi (v))/23 .
Now observe that Xi (v) = Ri (v)∪Si (v), where Ri (v) and Si (v) are the sources and sinks that arrived
before v in the MLAST for type i. By Lemma 4.1(d), d(v, Xi (v)) ≤ 2classi (v) = 2j . Combining this
with the above bound on d(u, v) gives us d(u, v) ≤ 2j−3 , as desired.
S
L(e) ⊇ Bi (v). Moreover, Ej (v) ∩ Ej (v 0 ) =
Claim 5.5. For every v ∈ Ri (j), we have e∈Ej (v):r∈L(e)
/
∅ for distinct v, v 0 ∈ Ri (j).
S
Proof. To prove the first part of the claim, observe that by definition of Ej (v), we have e∈Ej (v) L(e) ⊇
Bi (v). Thus, it suffices to show that for every v ∈ Ri (j) and each terminal u ∈ Bi (v), the edge
ej (v) does not contain r as a leaf. Suppose, towards a contradiction, that there exists u ∈ Bi (v)
such that r ∈ L(ej (u)). Since ej (u) has length 2j−4 , we have diam(L(ej (u)) ≤ 2j−3 ; moreover,
r, u ∈ L(ej (u)) and so d(u, r) ≤ 2j−3 . Now, Claim 5.4 implies that d(u, v) ≤ 2j−3 . Therefore,
d(v, r) ≤ d(u, v) + d(u, r) < 2j . However, this contradicts Lemma 4.1(d), which implies that
d(v, r) ≥ 2j . Thus, r ∈
/ L(ej (u)).
To prove the second part of the claim, suppose towards a contradiction, that there exist v, v 0 ∈ Ri (j)
and u ∈ Bi (v) and u0 ∈ Bi (v 0 ) such that ej (u) = ej (u0 ). By triangle inequality, d(v, v 0 ) ≤ d(u, v) +
d(u, u0 ) + d(u0 , v 0 ). Claim 5.4 implies that d(u, v), d(u0 , v 0 ) ≤ 2j−3 . Since u, u0 are leaves of the same
edge of length 2j−4 , we get d(u, u0 ) ≤ 2j−3 . Therefore, d(v, v 0 ) < 2j . On the other hand, Lemma
4.1(c) says that d(v, v 0 ) ≥ 2j . This gives us our desired contradiction.
With these claims in hand, we have
X
X
min{σi , βi−1 |L(e)|} ≥
e∈Ej :r∈L(e)
/

X

min{σi , βi−1 |L(e)|}

v∈Ri (j) e∈Ej (v):r∈L(e)
/

≥

X
v∈Ri (j)

17

min{σi , βi−1

X
e∈Ej (v):r∈L(e)
/

|L(e)|}

X

≥

min{σi , βi−1 |Bi (v)|}

v∈Ri (j)

X

≥

σi = σi |Ri (j)|,

v∈Ri (j)

where the first inequality follows from the second part of Claim 5.5, the third inequality from the
first part, and the last inequality from the fact that |Bi (v)| ≥ σi /βi−1 .
Having proved these two lemmas, we have that for every HST embedding T and every i, we have
ALGi ≤ O(1) OPTi (T ). Summing over all i and using Lemma 2.5, we have ALG ≤ O(1) OPT(T )
for any HST embedding T , and so ALG ≤ O(log k) OPT. This proves Theorem 1.1.

6

Multi-Commodity Spanners

In the online α-MCS problem, we are given a graph G = (V, E) with edge costs d(u, v) satisfying the
triangle inequality. Terminal pairs (s, t) arrive one-by-one. The goal is to maintain a minimum-cost
subgraph H such that
P dH (s, t) ≤ αd(s, t) for all terminal pairs (s, t). We say that H is β-competitive
if its cost d(H) = (u,v)∈H d(u, v) is at most β of the cheapest Steiner forest connecting the terminal
pairs. We recall our main theorem about multi-commodity spanners.
Theorem 1.5 (Online Spanner). There exists a deterministic online algorithm that given k pairs
of terminals, maintains a forest with cost O(log k) times the Steiner forest on the pairs, and a
stretch of O(log k) for distances between all given pairs of terminals. Moreover, the total number
of edges in the forest is O(k), i.e. linear in the number of terminals.
Note that this result is tight in several ways. Firstly, the solution is also a feasible Steiner forest,
and we know that any online Steiner forest algorithm has cost Ω(log k) times the cheapest Steiner
forest, hence we cannot improve the cost even at the expense of greater stretch. Moreover, there
exists a k-vertex unweighted graph with girth Ω( logloglogk k ) and size Ω(k log k) [LPS88]. Thus, we
cannot improve the stretch by much either. Finally, Ω(k) edges are needed to connect k terminals.
High-level overview. Our algorithm (Algorithm 4) is based on the Berman-Coulston online
Steiner forest algorithm. There are two key ingredients to the algorithm. First, it classify terminals
according to the distance to their mates: class(si ) = class(ti ) = blog2 d(si , ti )c. Let Yj be the set
of terminals with class at least j. Second, the algorithm maintains a clustering of Yj as follows. It
designates a subset Zj ⊆ Yj that are 2j /16-separated from each other as centers, and assigns each
v ∈ Yj to a cluster C(z) where z is the nearest center of Zj to u.
The rule for adding edges is as follows: if for any u, v ∈ Yj with d(u, v) ∈ [2j , 2j+1 ) has dH (u, v) >
4 log k · d(u, v) (i.e., the pair has large stretch in the current graph H), the algorithm adds the edge
(u, v), and connects u and v to their respective centers; we call the former an augmentation edge
and the latter bridge edges and account for them separately.
Let Aj be the set of augmentation edges (u, v) with d(u, v) ∈ [2j , 2j+1 ). First, we show that it
suffices to bound the cost and number of augmentation edges (Lemma 6.1). Since the diameter of
each cluster is at most 2j /8, each augmentation edge must connect two different clusters. Thus we
can think of a meta-graph where the nodes correspond to clusters and meta-edges correspond to
Aj . The bridge edges allow us to argue that if there is a short path in the meta-graph between
nodes corresponding to clusters C(z) and C(z 0 ), then there is a short path in H between every
u ∈ C(z) and v ∈ C(z 0 ) (Lemma 6.2). We then use this to show that there cannot be a cycle of
18

Figure 4: An example of the meta-graph. The circles represent clusters that are nodes of the metagraph. The dashed edges and solid edges represent bridge and augmentation edges, respectively.
Note that not all terminals in a cluster has a bridge edge to the center.
length less than log k in the meta-graph and so the total number of meta-edges is at most O(1)
times the number of nodes, i.e. |Aj | ≤ O(|Zj |). Finally, we use the separation of Zj to show that
2j |Zj | = O(OPT) via a ball-packing argument (LemmaP6.5), and complete the analysis of the
algorithm’s cost. To bound the total number of edges j |Aj |, we use a charging scheme that
charges |Aj | to a carefully-chosen set of terminals and show that across all distance scales j, the
total charge received by each terminal is O(1).
Algorithm 4 Online (4 log k)-MCS
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

6.1

Aj ← ∅, Bj ← ∅, Zj ← ∅ for all j; H ← ∅;
while (si , ti ) arrives do
Define class(si ) = class(ti ) = blog d(si , ti )c
for j = 0 up to j = blog d(si , ti )c do
for u ∈ {si , ti } do
if d(u, z) ≥ 2j /16 for every center z ∈ Zj then
Add u to Zj
Define a new cluster C(u) = {u}
else
Choose z ∈ Zj closest to u and add u to C(z)
for u, v such that min{class(u), class(v)} ≥ j and d(u, v) ∈ [2j , 2j+1 ) do
if dH (u, v) > 4 log k · d(u, v) then
Add augmentation edge (u, v) to Aj and H
Let z, z 0 ∈ Zj such that u ∈ C(z), v ∈ C(z 0 )
Add bridge edges (u, z) and (v, z 0 ) to Bj and H

Analysis

To analyze Algorithm 4, we use a “shadow” algorithm that builds a family of O(log k) meta-graphs
Fj , one for each length scale 2j . Whenever the algorithm adds a new cluster—i.e., it adds a new
center z to Zj —the shadow algorithm creates a new node in Fj corresponding to C(z). We use
C(z) to refer to both the cluster as well as the corresponding node in Fj . Whenever Algorithm 4
adds an edge (u, v) to Aj , the shadow algorithm adds the meta-edge (C(z), C(z 0 )) where u ∈ C(z)
and v ∈ C(z 0 ). This is well-defined since u, v have class at least j and every terminal of class at
least j belongs to some cluster C(z) for z ∈ Zj . Furthermore, since the diameter of a cluster is less
than 2j /8, and each edge of Aj has length at least 2j , there are no self-loops. See Figure 4 for an
illustration.
19

Note that it suffices to consider the augmentation edges to bound the cost of H as well as the
number of edges in H. Indeed, every bridge edge in Bj has a corresponding augmentation edge
in Aj , and each augmentation edge corresponds to at most two bridge edges (of no greater cost).
This proves the following lemma.
P
P
Lemma 6.1. d(H) ≤ j 2j+1 · 3|Aj | and |E(H)| ≤ j 3|Aj |.
The following lemma relates distances in the meta-graph Fj to distances in H and G, and is key
to bounding d(H) and |E(H)|.
Lemma 6.2. If there is a path of ` meta-edges in Fj between nodes C(z) and C(z 0 ), then
1. dH (z, z 0 ) < (3` + 1) · 2j ;
2. d(u, v) < 2j /8 + (3` + 1) · 2j for every u ∈ C(z) and v ∈ C(z 0 ).
Proof. Let the nodes along the path in Fj be C(z1 ), C(z2 ), . . . , C(zk+1 ), where z = z1 and zk+1 = z 0 .
Let the corresponding augmentation edges be (u1 , v1 ), . . . , (uk , vk ) where u1 ∈ C(z1 ), vk ∈ C(zk+1 )
and vi , ui+1 ∈ C(zi ) for 1 ≤ i ≤ k. Note that each augmentation edge (ui , vi ) has two corresponding
bridge edges (ui , zi ) and (vi , zi+1 ).
We will now show that there is a short path in H from u to v via these augmentation and bridge
edges. Consider the path P in H from z1 to z`+1 consisting of these augmentation edges and their
corresponding bridge edges. There are ` augmentation edges and they have length at most 2j+1
each. There are 2` bridge edges and they have length at most 2j /16. Therefore, d(P ) ≤ 3` · 2j+1 .
This proves the first part of the lemma.
We now turn to proving the second part of the lemma. Observe that d(u, v) ≤ d(u, z) + d(z, z 0 ) +
d(z 0 , v). Now d(z, z 0 ) ≤ dH (z, z 0 ) ≤ (3` + 1) · 2j , from the first part of the lemma. We also
have d(u, z), d(z 0 , v) ≤ 2j /16 by definition of the clusters. Thus, d(u, v) ≤ 2j /8 + (3` + 1) · 2j , as
desired.
With this lemma in hand, we can lower-bound the girth of Fj .
Lemma 6.3 (Girth Bound). The girth of the meta-graph Fj is at least log k.
Proof. Suppose, towards a contradiction, that the meta-graph has a cycle of length less than log k.
Suppose that (C(z), C(z 0 )) is the meta-edge of the cycle that was added last, and (u, v) ∈ Aj is the
corresponding augmentation edge with u ∈ C(z) and v ∈ C(z 0 ). The edge (u, v) was added during
the j-th iteration of the outer for loop. Consider the state of Algorithm 4 and the meta-graph
right before (u, v) was added to H and (C(z), C(z 0 )) was added to Fj . At this time, there is a
path between nodes C(z) and C(z 0 ) in Fj with less than log k edges, so by Lemma 6.2, we have
dH (u, v) < 4 log k · 2j ≤ 4 log k · d(u, v). However, this contradicts the condition for adding (u, v)
to Aj and so Fj has girth at least log k.
Combining the previous lemma with the following result from extremal graph theory will allow us
to bound |Aj | later.
Lemma 6.4. [Bol04] Every graph on N vertices and girth k has at most O(N 1+2/(k−1) ) edges.
Let OPT be the cost of the optimal Steiner forest for the n terminal pairs.
P j+1
P
Lemma 6.5 (Cost Bound).
|Aj | ≤ O(1) j 2j+1 |Zj | ≤ O(log k) OPT.
j2
20

Proof. By Lemmas 6.3 and Lemma 6.4, we have |Aj | ≤ O(1)|Zj |. Now we bound OPT in terms of
|Zj |. Place a ball of radius 2j /32 around each z ∈ Zj . Since for any z, z 0 ∈ Zj , d(z, z 0 ) ≥ 2j /16,
these balls are disjoint. For any z ∈ Zj , the distance from z and its mate is at least 2j so the optimal
solution has a path of length at least 2j /32 that is contained P
in the ball around
This implies
P z.
j
j+1
j+1
that OPT ≥ (2 /32) · |Zj |. Putting all of this together, we have j 2 |Aj | ≤ j 2
· O(1)|Zj | ≤
O(log k) OPT.
P
We now turn to bounding the number of edges |E(H)| = j |Aj |. The main idea is to find for
each scale j, a subset of terminals Xj0 such that |Aj | ≤ O(1)|Xj0 |, and each terminal belongs in Xj0
for a constant number of scales j. This allows us to charge |Aj | to the terminals in Xj0 for each j,
and each terminal only receives a charge of O(1) across all j. Define Cj = {C(z) : z ∈ Zj }, the set
of clusters corresponding to centers Zj . First, we show that there cannot be any large subset of
clusters in Cj that are far apart from each other. In particular, for any such subset Cj+ ⊆ Cj , |Aj |
is at most twice the number of remaining clusters Cj \ Cj+ .
Lemma 6.6. Let Cj+ be any subset of Cj such that for any clusters C(z), C(z 0 ) ∈ Cj and terminals
u ∈ C(z) and v ∈ C(z 0 ), we have d(u, v) ≥ 8 · 2j . Let Cj− = Cj \ Cj+ be the remaining clusters. Then,
we have |Aj | ≤ 2|Cj− |.
Proof. Without loss of generality, we assume that the meta-graph Fj is connected (otherwise we
can apply the same argument on each component of Fj ). We begin by showing that |Cj+ | ≤ |Cj− |.
The second part of Lemma 6.2 implies that in Fj , if there exists a path consisting of at most 2
meta-edges between meta-nodes C(z) and C(z 0 ), then d(u, v) < 8·2j for all u ∈ C(z) and v ∈ C(z 0 ).
Thus, any path between two meta-nodes C(z), C(z 0 ) ∈ Cj+ has to contain at least 3 meta-edges.
This implies that every meta-node in Cj+ can only have meta-nodes in Cj− as neighbors, and no two
meta-nodes of Cj+ can share the same neighbor in Cj− . Since Fj is connected, we have that each
meta-node in Cj+ must have at least one neighbor in Cj− . Putting all these facts together gives us
|Cj+ | ≤ |Cj− |.
By Lemmas 6.3 and Lemma 6.4, we have |Aj | ≤ O(1)|Zj |. Since |Zj | = |Cj | and |Cj+ | ≤ |Cj− |, we
have |Aj | ≤ 2|Cj− |.
P
Lemma 6.7 (Sparsity Bound).
j |Aj | ≤ O(k).
Proof. We can easily construct a family of nets Nj , one for each j, such that Nj is a 2j /32-net and
is nesting, i.e. Nj ⊆ Nj−1 for all j.
First, we claim that each cluster C(z) ∈ Cj contains at least one net point v ∈ Nj . Suppose, towards
a contradiction, that there exists a cluster C(z) ∈ Cj such that C(z) ∩ Nj = ∅. Consider a net point
v ∈ Nj . Since each terminal is added to the cluster of the closest center in Zj and v is not assigned
to z, it must be the case that d(v, z) ≥ 2j /32; otherwise, z would have been the closest center to v
because d(z, z 0 ) ≥ 2j /16 for every z 0 ∈ Zj . Therefore, every net point v ∈ Nj has d(v, z) ≥ 2j /32,
but this contradicts the fact that Nj is a 2j /32-net. Thus, each cluster in Cj contains at least one
net point v ∈ Nj .
Next, for each terminal v, we define its rank to be the largest j such that v ∈ Nj . Let Nj+ = Nj+9
and Xj0 = Nj \ Nj+ . Note that because of the nesting property of the nets, the terminals in Xj0
are exactly those with rank between j and j + 9. Let Cj+ be the subset of Cj that intersects with
Nj+ and Cj− = Cj \ Cj+ . Now, for every C(z), C(z 0 ) ∈ Cj+ and u ∈ C(z) and v ∈ C(z 0 ), we have

21

d(u, v) ≥ d(z, z 0 ) − d(u, z) − d(v, z 0 ) ≥ 2j+9 /32 − 2 · 2j /16 ≥ 2j+3 . Therefore, by Lemma 6.6, we
have |Aj | ≤ 2|Cj− |.
Now, every cluster C ∈ Cj− contains a terminal of Xj0 ; this is because every cluster contains at least
one terminal of Nj and clusters in Cj− do not contain any terminal of Nj+ . Since the clusters Cj−
P
P
are disjoint, we have |Cj− | ≤ |Xj0 |. We now have j |Aj | ≤ 2 j |Xj0 |. Observe that every terminal
0
is contained in Xj0 for at most a constant numberPof scales j (each terminal
P v ∈ Xj has rank(v) ∈
0
[j, j + 9]). Since there are 2k terminals, we have j |Xj | ≤ O(k) and so, j |Aj | ≤ O(k).
Lemmas 6.1, 6.5 and 6.7 give us Theorem 1.5.
Handling lack of knowledge of k. Our Algorithm 4 requires the knowledge of the value of k in
determining when augmentation edges must be added, which is not available a priori in the online
setting. However, it is relatively straightforward to get over this by noting that the subgraph H
maintained by the algorithm can be decomposed into one set of edges for every distance scale j. At
a specific distance scale, the number of centers in Zj gives us a good lower bound on kj which can
be used in place of k in determining the stretch condition: in other words, we use 4 log kj in the
stretch condition when processing the loop for j, and update it whenever the number of clusters in
Zj doubles.

7

Randomized Oblivious Buy at Bulk

In this section, we describe our randomized algorithm for the oblivious case, where we don’t know
the buy-at-bulk function in advance, and hence have to give a solution that is simultaneously good
for all buy-at-bulk functions. Let us recall our main result for this section, Theorem 1.2:
Theorem 1.2 (Oblivious Buy-at-Bulk, Randomized). There exists a randomized online algorithm
for the buy-at-bulk problem that produces a routing P such that for all concave functions f ,


E costf (P ) ≤ O(log2 k) OPTf .
Recall that this guarantee can also be achieved by performing Bartal’s tree embeddings, but the
ideas we develop here will be crucial to getting the deterministic algorithm in §8.
For this section and the next, we use gi to denote the “rent-or-buy” concave function gi (x) =
min{2i , x} and write OPTi to be the cost of the optimal solution for gi . Given a routing solution P ,
we denote by costi (P ) the cost of P under gi . By Lemma 2.6 it suffices to show that simultaneously
for all gi ,
costi (P ) ≤ O(log2 k) OPTi .
This is what we show in the rest of this section and the next.

7.1

High-Level Description

We begin by reviewing the main ideas for approximating a fixed rent-or-buy function gi = min{x, 2i }
online. Essentially, it boils down to choosing a good set of “buy” terminals Xi (which includes the
root) online. The terminal set Xi is connected by buying the edges of an online Steiner tree Fi
on them. The remaining terminals are called “rent” terminals and are routed as follows: For each
rent terminal u, let Xi (v) be the set of bought terminals at the time of its arrival; the terminal u
is then routed to the nearest buy terminal v ∈ Xi (v) (the edge (u, v) is rented), and then via v’s
path to the root in Fi . Observe that the cost of buying edges is 2i d(Fi ) and the cost of renting
22

P
3
edges is v∈X
/ i d(v, Xi (v)). A key ingredient (see, e.g., [AAB04]) is the fact that if we choose each
terminal v to be a buy terminal with probability 2−i , then
X
2i d(Steiner(Xi )) +
d(v, Xi (v)) ≤ O(log k) OPTi .
(9)
v ∈X
/ i

But this approach requires knowing the particular function gi , whereas we need to oblivious, i.e.,
to be good for all gi simultaneously. This suggests the following approach to designing an online
oblivious algorithm. Firstly, we assign a type τ (v) to each terminal v at random: τ (v) = i with
probability 2−i . As before, we assign the root r to have type ∞. Thus, if we define Xi to be the
set of terminals with type at least i, then it satisfies Inequality (9).
Secondly, for each type i, we maintain an online spanner Fi on Xi using the algorithm from §6. We
think of the edges that belong to a spanner of type at least i as the edges that our solution buys
if it is given the i-th rent-or-buy function gi . Then, each terminal v is routed using a path P (v)
that goes through spanners of progressively higher type until we reach the root. Let Pi (v) be the
prefix of P (v) right before it enters a spanner of type at least i. This is the part of P (v) that will
be rented for gi . At a high level, the lightness and low distortion properties of the spanners will
allow us to prove that the routing P satisfies the following bounded cost properties for all i:
• Bounded buy cost: 2i d(Fi ) ≤ O(log k) Steiner(Xi );
P
• Bounded rent cost: v:τ (v)<i d(Pi (v)) ≤ O(log k)d(v, Xi (v)), i.e. the distance from v to Xi (v)
on the path P (v) is not much larger than the actual distance.
Some care needs to be taken in choosing which spanners to route through. Fix a terminal v, and
for each i ≥ τ (v), let wi be the nearest terminal of type at least i and call it the i-th waypoint for v.
A natural idea is to route from v to wτ (v)+1 using the spanner Fτ (v) , then from wτ (v)+1 to wτ (v)+2
using Fτ (v)+1 , and so on, until we reach the root. However, the problem is that even if we were to
route between consecutive waypoints wi , wi+1 using the direct edge (wi , wi+1 ), the total length of
the path before we can reach a given wi0 might be too large. To overcome this issue, we bypass
waypoints that are of roughly the same distance from v and route through a subset of waypoints
whose distances from v are geometrically increasing. See Algorithm 5 for a formal description of
our algorithm.

7.2

Analysis

We now analyze costi (P ). For each terminal v, define Xi (v) to be the subset of terminals of type
at least i when v arrived, excluding v itself.
P
P
Lemma 7.1. costi (P ) ≤ 2i i0 ≥i d(Fi0 ) + v:τ (v)<i d(Pi (v)).
P
Proof. Recall that costi (P ) = e∈E d(e) min{2i , loadP (e)}, where loadP (e) is the total number of
terminals v whose paths P (v) include e. We will divide the edges used by the routing into two sets
Ri and Bi , and think of Ri as the set of rented edges (i.e. we pay d(e) loadP (e) on edges
S e ∈ Ri ),
and BSi as the set of bought edges (i.e. we pay 2i d(e) per edge in Bi ). Define Ri = v Pi (v) and
Bi = v P (v) \ Pi (v). We have
X
X
costi (P ) =
d(e) min{2i , loadP (e)} ≤ 2i d(Bi ) +
d(e) loadP (e).
e∈E
3

e∈Ri

We will actually need a stronger version, Lemma 7.2

23

w3 = r

w2

w1
w0 = v
20
21
22
23

Figure 5: The arrow from wi to wi+1 represents the shortest path between wi (v) and wi+1 (v) in
Fτ (wi ) . Note that it is possible for a ring (in this figure, the fourth ring) to not have a waypoint.

Algorithm 5 Randomized Online Oblivious Algorithm for Buy-at-Bulk
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

Initialize Xi ← ∅, Fi ← ∅ for all i
Set τ (r) ← ∞
while terminal v arrives do
Choose a random type τ (v), with τ (v) = i w.p. 2−i
For i ≤ τ (v), add v to Xi and update spanner Fi to include v
For i > τ (v), define waypoint wi to be terminal of Xi nearest to v
Set initial waypoint to be v
for j = 0 up to blog d(v, r)c do
Define the ring Rj = {wi : d(v, wi ) ∈ [2j , 2j+1 )}
if Rj 6= ∅ then
Choose waypoint wi in Rj of highest type and route from current waypoint wi0 to wi
along shortest path in Fi0

24

S
P
Since P (v) \ Pi (v) ⊆ i0 ≥i Fi0 , we have that 2i d(Bi ) ≤ 2i i0 ≥i d(Fi0 ). Now observe that for each
e ∈ Ri , loadP (e) is exactly the number of terminals v of type less than i with
P Pi (v) 3 e. This is
because
P
(v)
=
6
∅
only
for
terminals
v
of
type
less
than
i.
Thus,
we
have
i
e∈Ri d(e) loadP (e) =
P
d(P
(v)).
i
v:τ (v)<i
We define Steiner(S) to be the cost of the optimal Steiner tree for terminals S.
Lemma 7.2. We have that
1. E[2i Steiner(Xi )] ≤ OPTi and
P
2. E[ v d(v, Xi (v))] ≤ O(log k) OPTi .
Proof. We begin with the first part of the lemma. For terminal v ∈ X, let Pi∗ (v) be the path to
the root in OPTi . Define Bi∗ to be the set of edges over which at least 2i terminals are routed, and
for each v, define R∗i (v) = Pi∗ (v) \ Bi∗ . The cost of the optimal solution is
X
OPTi = 2i d(Bi∗ ) +
d(R∗i (v)).
v∈X

Define Hi =

S

v∈Xi

Pi∗ (v). Since Hi is a Steiner tree for terminals Xi ,

 X
∗
i
i
∗
i
d(Ri (v))
E[2 Steiner(Xi )] ≤ 2 d(Bi ) + E 2
v∈Xi
i

d(Bi∗ )

i

d(Bi∗ )

≤2

+2

i

X

d(R∗i (v)) · Pr[v ∈ Xi ]

v

≤2

+

X

d(R∗i (v)) = OPTi .

v

This proves the first part of the lemma.


P
i
We now turn to the second part of the lemma. For this, we will show that E 2
v∈Xi d(v, Xi (v)) =


P
P
E
v∈Xi d(v, Xi (v)) ≤ O(log k) Steiner(Xi ), and apply the first part
v d(v, Xi (v)) , then prove
of the lemma. By linearity of expectation,
 X

X
i
E 2
d(v, Xi (v)) = 2i
E[d(v, Xi (v)) · 1{v ∈ Xi }]
v

v∈Xi

= 2i

X

E[d(v, Xi (v))] · Pr[v ∈ Xi ]

v

=E

X


d(v, Xi (v))

v

where the second equality follows from the fact that whether v ∈ Xi is independent of d(v, Xi (v)),
and the last equality from the fact that Pr[v ∈ Xi ] = 1/2i .
P
Next, we prove v∈Xi d(v, Xi (v)) ≤ O(log k) Steiner(Xi ). Consider the online Steiner tree instance
defined on terminals Xi . The costPof the greedy algorithm, which connects each terminal to the nearest previous terminal, is exactly v∈Xi d(v, Xi (v)). The fact
P that the greedy algorithm is O(log k)competitive for the online Steiner tree problem implies v∈Xi d(v, Xi (v)) ≤ O(log k) Steiner(Xi ).
25

Therefore,
X

 X

i
E
d(v, Xi (v)) = E 2
d(v, Xi (v)) ≤ O(log k)E[2i Steiner(Xi )] ≤ O(log k) OPTi .
v

v∈Xi

This completes the proof of the second part of the lemma.
In the following, denote by Pi (v) the prefix of P (v) right before it enters a spanner Fi0 with i0 ≥ i.
Lemma 7.3. For every i > τ (v), we have d(Pi (v)) ≤ O(log k)d(v, Xi (v)).
Proof. Note that wi is the nearest terminal of Xi (v) so d(v, wi ) = d(v, Xi (v)). Define W to be
the subset of waypoints wi such that wi is the waypoint of highest type in some ring Rj , and
I = {i : wi ∈ W }. For every type i0 > τ (v) that is not in I, there exists i ∈ I such that i > i0 and
d(v, wi ) ≤ 2d(v, wi0 ); moreover, since i > i0 , we have d(Pi0 (v)) ≤ d(Pi (v)). Therefore, it suffices to
prove d(Pi (v)) ≤ O(log k)d(v, wi ) for types i ∈ I.
For brevity, we abuse notation and write w` to denote the waypoint in W with `-th highest type;
F` to denote the spanner of type τ (w` ). Let P` (v) be the prefix of P (v) ending at w` . We now
show that d(P` (v)) ≤ O(log k)d(v, w` ).
Since P` (v) consists of the union of the P
shortest path between w`0 −1 and w`0 in F`0 −1 , for every
`0 < `, the length of P` (v) is d(P` (v)) = `0 ≤` dF`0 −1 (w`0 −1 , w`0 ). For every `0 < `, since F`0 −1 is a
spanner with stretch O(log k), we have
dF`0 −1 (w`0 −1 , w`0 ) ≤ O(log k)d(w`0 −1 , w`0 ) ≤ O(log k)(d(v, w`0 −1 ) + d(v, w`0 )).
Thus,
d(P` (v)) ≤ O(log k)

X

(d(v, w`0 −1 ) + d(v, w`0 )) ≤ O(log k)d(v, w` ),

`0 <`

where the last inequality follows from the fact that we chose W to contain at most one waypoint
per ring and the rings have geometrically increasing distances.
Lemma 7.4. E[costi (P )] = O(log2 k) OPTi .
 P

Proof. By Lemma 7.1, the expected cost of the algorithm’s solution is E[costi (P )] ≤ E 2i i0 ≥i d(Fi0 ) +
P

0
E
v:τ (v)<i d(Pi (v)) . Let i > i. Since d(Fi0 ) is a (log k)-competitive (log k)-spanner on Xi , we
have d(Fi0 ) ≤ O(log k) Steiner(Xi0 ). Together with the fact that Steiner(Xi0 ) ≤ Steiner(Xi ) (since
Xi0 contains Xi ), we have
X
 X

E 2i
d(Fi0 ) ≤ O(log k)
E[2i Steiner(Xi0 )] ≤ O(log2 k)E[2i Steiner(Xi )] ≤ O(log2 k) OPTi ,
i0 ≥i

i0 ≥i

where the last inequality follows from Lemma 7.2.
P

Next, we turn to bounding E
v:τ (v)<i d(Pi (v)) . By Lemmas 7.3 and 7.2, we have
E

 X
v:τ (v)<i


 X

d(Pi (v)) ≤ O(log k)E
d(v, Xi (v)) ≤ O(log2 k) OPTi .
τ (v)<i

26

8

Deterministic Oblivious Buy at Bulk

In this section, we present our deterministic algorithm for the oblivious setting, and prove Theorem
1.3.
Theorem 1.3 (Oblivious Buy-at-Bulk, Deterministic). There exists a deterministic online algorithm for the buy-at-bulk problem that produces a routing P such that for all concave functions
f,
costf (P ) ≤ O(log2.5 k) OPTf .
Our deterministic oblivious algorithm is based on the randomized version from §7 (Algorithm 5)
with two modifications. First, we remove the need for randomness by using the deterministic type
selection rule used by our non-oblivious algorithm from §5 (Algorithm 3). We can show that this
modification already yields an O(log3 k)-competitive algorithm. To get the competitive ratio down
to O(log2.5 k), we need to use a different routing scheme. For clarity of presentation, we first present
the simpler O(log3 k)-competitive algorithm and later (in Section 8.2) show how to modify it to
obtain the O(log2.5 k)-competitive algorithm of Theorem 1.3.

An O(log3 k)-competitive Algorithm

8.1

We will assign a type τ (v) to each terminal v, with the root having type τ (r) = ∞. As before, we use
Xi to denote the set of terminals with type at least i. We will also maintain a (log k, log k)-spanner
Fi on Xi .
Algorithm 6 Simpler Online Deterministic Oblivious Algorithm for Buy-at-Bulk
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

Initialize Xi ← ∅, Fi ← ∅ for all i
Set τ (r) ← ∞
while terminal v arrives do
for each type i do
Define classi (v) to be the highest j such that v is a level j center in spanner Fi if it were
to be included in Fi
classi (v) /23 }.
Define the ball Bi (v) =
 {u : d(u, v) ≤i 2
Assign type τ (v) = max i : |Bi (v)| ≥ 2 .
For i ≤ τ (v), update spanner Fi to include v
For i > τ (v), define waypoint wi to be terminal of Xi nearest to v
Set initial waypoint to be v
for j = 0 up to blog d(v, r)c do
Define the ring Rj = {wi : d(v, wi ) ∈ [2j , 2j+1 )}
if Rj 6= ∅ then
Choose waypoint wi in Rj of highest type and route from current waypoint wi0 to wi
along shortest path in Fi0

8.1.1

Analysis

Fix a type i. We will now show that costi (P ) ≤ O(log2 k) OPTi . As before, define Pi (v) to be the
segment of P (v) right before it enters a spanner Fi0 with i0 ≥ i. (Note that Pi (v) = ∅ if τ (v) ≥ i.)
P
P
P
i
i
By Lemma
7.1,
we
have
cost
(P
)
≤
2
d(P
(v)).
Next,
we
bound
2
0 ≥i d(Fi )+
i
i
i
v:τ
(v)<i
i0 ≥i d(Fi )
P
and v:τ (v)<i d(Pi (v)) separately.
27

Lemma 8.1.

P

v:τ (v)<i d(Pi (v))

≤ O(log2 k) OPTi .

Proof. Using the same argument as in the proof of Lemma 7.3 gives us that for every terminal v,
and type i > τ (v), we have d(Pi (v)) ≤ O(log k)d(v, Xi (v)). Thus,
X
X
d(v, Xi (v)).
d(Pi (v)) ≤ O(log k)
v:τ (v)<i

v:τ (v)<i

Using a similar proof as that of Lemma 5.2, we also have
X
d(v, Xi (v)) ≤ O(log k) OPTi .
v:τ (v)<i

Combining these two inequalities gives us the lemma.
P
Lemma 8.2. 2i i0 ≥i d(Fi0 ) ≤ O(log2 k) OPTi (T ) for any HST embedding T .
0
Proof. Let i0 > i. By Lemma 6.5 and the fact that class
Pi (v) is the highest level j such that v
is a level-j center in Fi0 , we have that 2i d(Fi0 ) ≤ O(1)2i v∈X 0 2classi0 (v) . Now, we would like to
i
say that the RHS of the previous inequality is at most O(1) OPTi0 (T ) for any HST embedding T .
We can prove this using a similar proof as in Lemma 5.3 if for every v with τ (v) ≥ i0 , we have
0
|Bi0 (v)| ≥ 2i . Unfortunately, this is not necessarily the case. A terminal v might have τ (v) ≥ i0 ,
0
i.e. it has at least 2τ (v) ≥ 2i terminals in its τ (v)-th ball Bτ (v) (v), but its i0 -th ball Bi0 might have
a radius much smaller than Bτ (v) (v) (i.e. classi0 (v) < classτ (v) (v)), and thus does not contain at
0
least 2i terminals. In this case, roughly speaking, we will charge the cost of including v in Fi0 to
the cost of including it in Fτ (v) .
0

More formally, for each type i0 , define Ai0 = {v ∈ Xi0 : |Bi0 (v)| ≥ 2i }, i.e. this is the set of terminals
who can “pay” to be included in spanner Fi0 .
Claim 8.3. Let v be a terminal with type τ (v) > i0 . If v ∈
/ Ai0 , then classi0 (v) < classτ (v) (v).
Proof. The balls Bτ (v) (v) and Bi0 (v) have radii 2classτ (v) (v)−3 and 2classi0 (v)−3 , respectively. By
0
definition of types, v ∈ Aτ (v) and so |Bτ (v) (v)| ≥ 2τ (v) ≥ 2i . Since v ∈
/ Ai0 , the radius of Bi0 (v)
must be smaller than the radius of Bτ (v) (v) and so classi0 (v) < classτ (v) (v).
Define N (v) = {i0 < τ (v) : v ∈ Xi0 \ Ai0 }, i.e. the set of types i0 for which v is included in spanner
Fi0 but could not pay to be included in Fi0 . Combining this with the above claim, we get


X
X X
X

d(Fi0 ) ≤ O(1)
2classi0 (v) +
2classτ (v) (v) 
i0 ≥i

i0 ≥i

v∈Ai0

= O(1)

X X

≤ O(1)

X X

v∈Xi0 \Ai0

2classi0 (v) +

i0 ≥i v∈Ai0

X
v∈Xi

2classi0 (v) + O(log k)

i0 ≥i v∈Ai0

≤ O(log k)

|N (v)| · 2classτ (v) (v)

X X

X

2classτ (v) (v)

v∈Xi

2classi0 (v)

i0 ≥i v∈Ai0

where the last inequality follows from the fact that v ∈ Aclassτ (v) (v) and τ (v) ≥ i.
28

Using a similar proof as in Lemma 5.3, we have 2i
2i

X

P

v∈Ai0

2classi0 (v) ≤ O(1) OPTi (T ). Thus,

d(Fi0 ) ≤ O(log2 k) OPTi (T ),

i0 ≥i

as desired.
With these two lemmas and Lemma 2.5 in hand, we have that ALG ≤ O(log3 k) OPTi and thus
the algorithm has competitive ratio O(log3 k).

8.2

Improving to O(log2.5 k)

We now describe the modified routing scheme. Suppose we know the number of terminals k of
the online
instance in advance (we will show how to remove this assumption at the end). Let
√
L = log k. The main idea is that instead of including each terminal v in spanner Fi for every
i ≤ τ (v), we only include v in Fi for τ (v) − L ≤ i ≤ τ (v). This helps us bound the number of
spanners that v is included but could not pay for by L. However, we now cannot reach all terminals
of type higher than i using spanner Fi . To cope with this, we will group the L2 different types
into consecutive intervals of length L. The routing for a terminal v now proceeds in several phases,
one per interval, starting from the interval containing τ (v). During phase t (corresponding to the
interval [tL, (t + 1)L]), we find a path Qt from the waypoint wtL (or v if the interval contains τ (v))
to w(t+1)L by passing through intermediate waypoints that belong to rings geometrically increasing
distances.
In the following, we write u ∈ Fi (v) to mean that u is a terminal included in spanner Fi before v
arrived.
Algorithm 7 Improved Online Deterministic Oblivious Algorithm for Buy-at-Bulk
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Initialize Xi ← ∅, Fi ← ∅ for all i
Set τ (r) ← ∞
while terminal v arrives do
for each type i do
Define classi (v) to be the highest j such that v is a level j center in spanner Fi if it were
to be included in Fi
classi (v) /23 }.
Define the ball Bi (v) =
 {u : d(u, v) ≤i 2
Assign type τ (v) = max i : |Bi (v)| ≥ 2 .
For τ (v) − L ≤ i ≤ τ (v), update spanner Fi to include v
For i > τ (v), define waypoint wi to be terminal of Fi nearest to v
Set initial waypoint to be v
for t such that τ (v) − 1 ≤ tL ≤ log k do
Define the ring Rj (t) = {wi : tL ≤ i ≤ (t + 1)L ∧ d(v, wi ) ∈ [2j , 2j+1 )}
Initialize Qt ← ∅
while current waypoint is not w(t+1)L do
if Rj (t) 6= ∅ then
Choose waypoint wi in Rj (t) of highest type and route from current waypoint wi0 to
wi along shortest path in Fi0
Add shortest path to Qt

29

Lemma 8.4. For each terminal v, we have

X
d(Pi (v)) ≤ O(log k) 


d(v, F(t+1)L (v)) + d(v, Fi (v)) .

t:τ (v)<(t+1)L≤i

Proof. Let Qt be the segment of P (v) starting from wtL (v) to w(t+1)L (v) and Qt (i) be the segment of Qt right before it enters a spanner Fi0 with i0 ≥ i. Using a similar proof as in Lemma
7.3, for every t and i ∈ [tL, (t + 1)L], we get that d(Qt (i)) ≤ O(log k)d(v, wi (v)) and d(Qt ) ≤
O(log k)d(v, w(t+1)L (v)). For each type i, define ti to be the integer such that i ∈ [ti L, (ti + 1)L).
We have


X
X
d(v, w(t+1)L (v)) + d(v, wi (v)) .
d(Qt )+d(Qti (i)) ≤ O(log k) 
d(Pi (v)) =
t:τ (v)<(t+1)L<i

t:τ (v)<(t+1)L<i

Lemma 8.5.

P

v:τ (v)<i d(Pi (v))

≤ O(log2.5 k) OPTi .

P
Proof. Using a similar proof as Lemma 5.2, we get that v:τ (v)<i0 d(v, Fi0 (v)) ≤ O(log k) OPTi0 .
Combining this with Lemma 8.4 gives us


X
X
X
X
d(Pi (v)) ≤ O(log k) 
d(v, F(t+1)L (v)) +
d(v, Fi (v))
v:τ (v)<i

t:(t+1)L<i v:τ (v)<(t+1)L


≤ O(log2 k) 

v:τ (v)<i


X

OPT(t+1)L + OPTi 

t:(t+1)L<i

≤ O(log

2.5

k) OPTi ,

where the last inequality follows from the fact that√OPTi0 ≤ OPTi if i0 < i and that the number
of integers t such that (t + 1)L < i is at most L = log k.
P
Lemma 8.6. 2i i0 ≥i d(Fi ) ≤ O(log1.5 k) OPTi (T ) for any HST embedding T .
Proof. The proof of this lemma is similar to that of Lemma √
8.2 except that the total number of
types i0 such that v is included in spanner Fi0 is at most L = log k.
√
Removing the need to know k in advance. First, instead of using intervals of length log k,
we will use intervals between perfect squares. In particular, the t-th interval
is [t2 , (t + 1)2 ]. Second,
√
each terminal v is included in spanners Fi where τ (v) ≥ i ≥ τ (v) − i.

9

Conclusions

Several open questions remain: can we do better than O(log2 k) for the oblivious randomized
case, and O(log2.5 k) for the oblivious deterministic case? Can we get online constructions of tree
embeddings with stretch better than O(log k log ∆)?

30

References
[AA97]

Baruch Awerbuch and Yossi Azar. Buy-at-bulk network design. In 38th Annual Symposium
on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19-22,
1997, pages 542–547, 1997.

[AAB04]

Baruch Awerbuch, Yossi Azar, and Yair Bartal. On-line generalized steiner problem. Theor.
Comput. Sci., 324(2-3):313–324, 2004.

[AKPW95] Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its
application to the k-server problem. SIAM J. Comput., 24(1):78–100, 1995.
[And04]

Matthew Andrews. Hardness of buy-at-bulk network design. In 45th Symposium on Foundations
of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings, pages 115–
124, 2004.

[Bar96]

Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In
37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont,
USA, 14-16 October, 1996, pages 184–193, 1996.

[Bar98]

Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the Thirtieth
Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998,
pages 161–168, 1998.

[Bar04]

Yair Bartal. Graph decomposition lemmas and their role in metric embedding methods. In
Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17,
2004, Proceedings, pages 89–97, 2004.

[BC97]

Piotr Berman and Chris Coulston. On-line algorithms for steiner tree problems (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 344–353, 1997.

[Bol04]

Béla Bollobas. Extremal Graph Theory. Dover Publications, Incorporated, 2004.

[ECKP15] Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, and Debmalya Panigrahi. Online buy-at-bulk network design. In IEEE 56th Annual Symposium on Foundations of Computer
Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 545–562, 2015.
[FRT04]

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary
metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004.

[GE05]

Ashish Goel and Deborah Estrin. Simultaneous optimization for concave costs: Single sink
aggregation or single source buy-at-bulk. Algorithmica, 43(1-2):5–15, 2005.

[GHR06]

Anupam Gupta, Mohammad Taghi Hajiaghayi, and Harald Räcke. Oblivious network design. In
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA
2006, Miami, Florida, USA, January 22-26, 2006, pages 970–979, 2006.

[GI06]

Fabrizio Grandoni and Giuseppe F. Italiano. Improved approximation for single-sink buy-atbulk. In Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata,
India, December 18-20, 2006, Proceedings, pages 111–120, 2006.

[GKK+ 01] Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. Sibel Salman, and Amitabh Sinha
II. On the integrality gap of a natural formulation of the single-sink buy-at-bulk network design
problem. In Integer Programming and Combinatorial Optimization, 8th International IPCO
Conference, Utrecht, The Netherlands, June 13-15, 2001, Proceedings, pages 170–184, 2001.
[GKR03]

Anupam Gupta, Amit Kumar, and Tim Roughgarden. Simpler and better approximation algorithms for network design. In 35th STOC, pages 365–372, 2003.

[GMM09]

Sudipto Guha, Adam Meyerson, and Kamesh Munagala. A constant factor approximation for
the single sink edge installation problem. SIAM J. Comput., 38(6):2426–2442, 2009.

31

[GP12]

Ashish Goel and Ian Post. One tree suffices: A simultaneous o(1)-approximation for single-sink
buy-at-bulk. Theory of Computing, 8(1):351–368, 2012.

[GRS11]

Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanità. From uncertainty to nonlinearity:
Solving virtual private network via single-sink buy-at-bulk. Mathematics of Operations Research,
36(2):185–204, 2011.

[IW91]

Makoto Imase and Bernard M. Waxman. Dynamic steiner tree problem. SIAM J. Discrete
Math., 4(3):369–384, 1991.

[JR09]

Raja Jothi and Balaji Raghavachari. Improved approximation algorithms for the single-sink
buy-at-bulk network design problems. J. Discrete Algorithms, 7(2):249–255, 2009.

[KRY95]

Samir Khuller, Balaji Raghavachari, and Neal E. Young. Balancing minimum spanning trees
and shortest-path trees. Algorithmica, 14(4):305–321, 1995.

[LPS88]

Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica,
8(3):261–277, 1988.

[MP98]

Yishay Mansour and David Peleg. An approximation algorithm for minimum-cost network
design. In Robust Communication Networks: Interconnection and Survivability, Proceedings of a
DIMACS Workshop, New Brunswick, New Jersey, USA, November 18-20, 1998, pages 97–106,
1998.

[SCRS97]

F. Sibel Salman, Joseph Cheriyan, R. Ravi, and S. Subramanian. Buy-at-bulk network design:
Approximating the single-sink edge installation problem. In Proceedings of the Eighth Annual
ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana.,
pages 619–628, 1997.

[Tal02]

Kunal Talwar. The single-sink buy-at-bulk LP has constant integrality gap. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA,
USA, May 27-29, 2002, Proceedings, pages 475–486, 2002.

[Umb15]

Seeun Umboh. Online network design algorithms via hierarchical decompositions. In Proceedings
of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San
Diego, CA, USA, January 4-6, 2015, pages 1373–1387, 2015.

32

