Authors Ashish Goel, Ian Post,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368
www.theoryofcomputing.org
S PECIAL ISSUE IN HONOR OF R AJEEV M OTWANI
One Tree Suffices:
A Simultaneous O(1)-Approximation for
Single-Sink Buy-at-Bulk
Ashish Goel∗ Ian Post†
Received: September 14, 2010; published: July 20, 2012.
Abstract: We study the single-sink buy-at-bulk problem with an unknown cost function.
We wish to route flow from a set of demand nodes to a root node, where the cost of routing x
total flow along an edge is proportional to f (x) for some concave, non-decreasing function
f satisfying f (0) = 0. We present a simple, fast, combinatorial algorithm that takes a set
of demands and constructs a single tree T such that for all f the cost f (T ) is a 47.45-
approximation of the optimal cost for that particular f . This is within a factor of 2.33 of the
best approximation ratio currently achievable when the tree can be optimized for a specific
function. Trees achieving simultaneous O(1)-approximations for all concave functions were
previously not known to exist regardless of computation time.
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25, 68R10
Key words and phrases: network design, buy-at-bulk, simultaneous optimization
1 Introduction
Many natural network design settings exhibit some form of economies of scale that reduce the costs
when many flows are aggregated together. We may benefit from cheaper bandwidth when laying high
∗ Research funded by an NSF IIS grant, by funds from Google, Microsoft, and Cisco, a 3-COM faculty fellowship, and by
the ARL Network Science CTA.
† Research funded by an NSF IIS grant.
2012 Ashish Goel and Ian Post
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a015
A SHISH G OEL AND I AN P OST
capacity network links [2], reduced infrastructure costs or bulk discounts for shipping large amounts of
goods together [29, 30], or summarization and compression of correlated information flows [26]. These
scenarios are known in the literature as buy-at-bulk problems. In a general buy-at-bulk problem we are
given a graph and a set of demands for flow between nodes. The cost of routing a total of xe flow along
an edge e with length `e is `e f (xe ) for some function f , and the goal is to find a collection of routes
satisfying the demands that minimizes the total cost ∑e `e f (xe ). To model the economies of scale, we
assume f is concave and monotone non-decreasing.
We will focus on single-sink (or single-source) case, where all demands must be routed to a given
root. When f is known, the problem becomes the well-studied single-sink buy-at-bulk (SSBaB) problem.
SSBaB is NP-hard—it generalizes the Steiner tree problem—but constant-factor approximations are
known for any given f (e. g., [17, 18, 16]). The special case where f has the form f (x) = min{x, M} for
some M (edges can be “rented” for linear cost or “bought” for a fixed cost) is known as the single-sink
rent-or-buy (SSRoB) problem and has also received significant attention (e. g., [24, 7]).
Buy-at-bulk algorithms produce trees that are heavily tailored to the particular function at hand, but
in some scenarios f may be unknown or known to change over time. One setting where this arises is in
aggregation of data in sensor networks. The degree of redundancy among different sensor measurements
may be unknown, or the same network may be used for aggregating different types of information
with different amounts of redundancy. In other situations rapid technological advancement may cause
bandwidth costs to change drastically over time. Further, in the interest of simplifying the design
process and building robust networks, it may be useful to decouple the problem of designing the network
topology from that of determining the exact characteristics of the information or goods flowing through
that network. In these settings it is desirable to find a single tree that is simultaneously good for all
cost-functions, and from a theoretical perspective, the existence of such trees would reveal surprising
structure in the problem.
There are two natural objective functions which capture the idea of simultaneous approximation
for multiple cost functions. Let F be the set of all concave, monotone non-decreasing cost functions f
satisfying f (0) = 0 and T f∗ be the optimal routing graph for f . Note that due to the concavity of f , we
may assume that T f∗ is a tree (Lemma 1 in [2]). For a routing tree T , we use the shorthand f (T ) to denote
the cost of T under function f . Formally, f (T ) = ∑e `e f (xe ), where xe is the amount of flow T sends on
edge e. Let R be a randomized algorithm that returns a feasible routing tree T . First, we could try to
minimize the quantity
ER [ f (T )]
sup ∗ (1.1)
f ∈F f (T f )
which we call the oblivious approximation ratio. If the oblivious ratio is small, then R returns a distribution
that works well in expectation for any f . However, there may be no sample from this distribution that
works for everything: for any tree T there may be functions for which f (T ) is expensive.
To circumvent this problem we can work with the much stronger simultaneous approximation ratio.
For a deterministic or randomized algorithm A that returns a tree TA the simultaneous ratio of A is defined
as:
" #
f (TA )
EA sup ∗ (1.2)
f ∈F f (T f )
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 352
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
A bound on the simultaneous ratio subsumes one on the oblivious ratio and proves there exists a single
tree that is simultaneously good for all f .
We emphasize that the distinction between the simultaneous and oblivious objectives is not a tech-
nicality in the objective but rather a fundamental difference and that the gap between these ratios can
be large. Consider the problem of embedding arbitrary metrics into tree metrics, another problem that
requires bounding the cost under many different functions (i. e., distortion of each edge). It is well-known
that distributions over trees can achieve O(log n) expected distortion for all edges [10] but that even for
simple graphs like the n-cycle no single tree can do better than Ω(n) distortion [27]. Therefore, the ratio
between maximum expected distortion and the expected maximum distortion is Ω(n/ log n) in this case.
Goel and Estrin [12] introduced the problem of simultaneous SSBaB and gave an algorithm with an
O(log D) bound on the simultaneous ratio (1.2), where D is the total amount of demand. Prior to our
work,1 it was not known whether a simultaneous ratio (or even the weaker oblivious ratio) of O(1) could
be achieved regardless of computation time. In this paper we give the first constant guarantee on the
simultaneous ratio, resolving the major open question of Goel and Estrin and Goel and Post [12, 13].
Several aspects of our algorithm and analysis bear mentioning. First,√given a deterministic λ -
approximation for SSRoB, we achieve a simultaneous ratio of (1 + ε)(8 + 4 5)λ , and we achieve this
ratio in expectation if the approximation is randomized. This results in a deterministic algorithm with
a simultaneous ratio of 55.58, and using a randomized SSRoB approximation, our simultaneous ratio
improves to 47.45 in expectation, which is within a factor of 2.33 of the current best approximation for
normal SSBaB of 20.42 [16]. Second, the algorithm is entirely combinatorial, and our analysis is short
and simple, no more complex than the analysis of a normal SSBaB algorithm. Third, using a deterministic
SSRoB approximation with a runtime of t(n, m) for a graph with n nodes and m edges, our runtime is
only O((t(n, m) + m + n log n) log D) where D is the total demand. If the SSRoB algorithm is randomized,
the runtime increases to O((t(n, m) log log D + m + n log n) log D).
The algorithm is no more complex than one for SSBaB, and at a high level, if not in the details, it
follows the template of many SSBaB algorithms. We first find approximate trees for a set of rent-or-buy
basis functions and divide the edges of each tree into rent and buy costs based on whether the rent-or-buy
function has leveled off on an edge. We prune this set to obtain a subset L of trees and corresponding
cost functions whose total rent costs are increasing geometrically while total buy costs are dropping
geometrically, and then prove it suffices to simultaneously approximate only the functions in L. Each
tree in L has a set of core nodes spanned by edges that are bought, and these cores define a series of tree
layers, which we stitch together using light approximate shortest-path trees (LASTs) [25] to approximate
both the minimum spanning tree (MST) and shortest-path tree. Finally, we consider any layer in the tree.
Using the geometrically changing costs and the properties of the LAST construction, we conclude that
everything within the layer is an approximate MST, and everything outside approximates the shortest-path
tree cost.
1 This submission combines two conference publications, in which we reduced first the oblivious ratio [13] and subsequently
the simultaneous ratio [14] to O(1); our exposition follows the latter of these two publications.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 353
A SHISH G OEL AND I AN P OST
1.1 Related work
The SSBaB problem was first posed by Salman et al. [29, 30], and the first general approximation
algorithm was given by Awerbuch and Azar [3], who used metric tree embeddings [4] to achieve an
O(log2 n) ratio, later improved to O(log n) using better embeddings by Bartal [5] and Fakcharoenphol et
al. [10]. Guha et al. [17, 18] gave the first constant approximation, and follow-up work by Talwar [32],
Gupta et al. [21], Jothi and Raghavachari [23], Grandoni and Italiano [15], and Grandoni and Rothvoß [16]
has since reduced the constant to 20.42. Most recent algorithms for SSBaB (and several related problems)
are based on the sample and augment framework of Gupta et al. [21]. Many algorithms using this
framework have been derandomized by van Zuylen [33].
The special case of SSRoB has also been extensively studied, often as a special case of the connected
facility location problem. The first constant factor approximation was given by Ravi and Salman [28] as a
special case of the traveling purchaser problem. Karger and Minkoff [24] gave an alternate algorithm and
introduced connected facility location. Gupta et al. improved the approximation to 9.01 [20], Swamy and
Kumar to 4.55 [31], and Gupta et al. to 3.55 [21]. Gupta et al. [22] derandomized the 3.55-approximation
to achieve a 4.2-approximation. Eisenbrand et al. [7] developed a randomized 2.92-approximation, which
recently improved to 2.8 using the 1.39-approximation for Steiner tree of Byrka et al. [6]. Since we
employ the 2.8-approximation, and the claimed ratio does not currently appear elsewhere in the literature,
we present the brief calculation deriving this value in Section 5. Both Williamson and van Zuylen [34]
and Eisenbrand et al. [7] independently derandomized the 2.92-approximation to achieve a deterministic
3.28-approximation.
The problem of simultaneous approximation for multiple cost functions has been studied using both
the oblivious and simultaneous objectives. Goel and Estrin [12] were the first to explicitly pose the
question of simultaneous approximations and gave an algorithm with an O(log D) simultaneous guarantee.
Prior to that Khuller et al. [25] gave an algorithm to simultaneously approximate the two extreme cost
functions f (x) = 1 and f (x) = x—a result which plays an important role in this paper—and metric tree
embeddings had been applied to SSBaB [3, 10] to achieve an O(log n) bound for the oblivious objective.
Enachescu et al. [8] gave an O(1) simultaneous guarantee for the special case of grid graphs with some
spatial correlation. Gupta et al. [19] and Englert and Räcke [9] have studied several generalizations of the
problem where both the demands and function are unknown, and multiple sinks are allowed. In these
settings the guarantee is generally O(log n) or O(polylog n).
2 Notation and preliminaries
Formally, we are given a graph G = (V, E) with edge lengths `e for e ∈ E, a root node r, and a set of
demand nodes D ⊆ V with integer demands dv . The total demand is D = ∑v dv . We want to route dv flow
from each v to r as cheaply as possible, where the cost of routing xe flow along edge e is `e f (xe ) for some
unknown, concave, monotone increasing function f satisfying f (0) = 0. Not knowing f , our objective is
to find a feasible tree T minimizing sup f f (T )/ f (T f∗ ), where T f∗ is the optimal graph for f .
We first show that we can restrict our analysis to a smaller class of basis functions, a technique
originally introduced by Goel and Estrin [12]. Let ε > 0 be a small constant that will trade off the runtime
and the approximation ratio, and K = dlog1+ε De. For 0 ≤ i ≤ K, define Mi = (1+ε)i , Ai (x) = min{x, Mi },
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 354
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
and Ti∗ as the optimal tree for Ai . By the monotonicity and concavity of f , whenever Mi ≤ x ≤ Mi+1 we
have f (Mi ) ≤ f (x) ≤ f (Mi+1 ) ≤ (1 + ε) f (Mi ), so with a loss of only a factor of 1 + ε we can interpolate
between f (Mi ) and f (Mi+1 ) and assume f is piecewise linear with breakpoints only at powers of 1 + ε.
Such a piecewise linear function can be written as a nonnegative linear combination f (x) = ∑i ai Ai (x) of
{Ai }0≤i≤K by setting coefficients ai equal to the changes in slope: if the slope drops from δi to δi+1 at
(1 + ε)i it induces the term (δi − δi+1 )Ai (x). Now for a linear combination ∑i ai Ai (x) and a tree T
∗ Ai (T )
∑i ai Ai (T ) ∑i ai Ai (T ) ∑i ai Ai (Ti ) Ai (T ∗ ) Ai (T )
i
∗ ≤ ∗ = ∗ ≤ max
∑i ai Ai (T f ) ∑i ai Ai (Ti ) ∑i ai Ai (Ti ) i Ai (Ti∗ )
so it suffices to upper bound maxi Ai (T )/Ai (Ti∗ ).
We now define some notation and subroutines that will be important for our algorithm. The problem of
finding a good aggregation tree for the function Ai (x) = min{x, Mi } is an instance of the SSRoB problem,
and we can find a λ -approximate tree Ti , where λ is the best approximation ratio known, currently
equal to 2.8 using the algorithm of Eisenbrand et al. [7] and Byrka et al. [6]. In the case of randomized
algorithms, such as the current 2.8-approximation, we run the approximation O(log log D) times for each
value of i and pick the best output, which ensures that the probability of any of the O(log D) trees Ti being
worse than a (1 + ε)λ -approximation is at most a constant. The remainder of our algorithm is entirely
deterministic, so this is the only possibility of failure. To ensure a totally deterministic algorithm we can
alternately use the 3.28-approximation algorithm of Williams and van Zuylen [34] and Eisenbrand et
al. [7].
The cost Ai (Ti ) can be broken into two pieces, the rent cost and the buy cost, based on whether Ai is
maxed out at Mi :
Definition 2.1. For an aggregation tree Ti for cost function Ai with xe flow on edge e, the rent cost Ri and
normalized buy cost Bi are defined as
Ri = ∑ `e Ai (xe ) ,
e∈Ti , xe <Mi
Ai (xe )
Bi = ∑ `e = ∑ `e .
e∈Ti , xe ≥Mi Mi e∈Ti , xe ≥Mi
Note that edges composing Ri are scaled by the costs incurred, but edges in Bi are not; they use
unscaled edge lengths. The total cost of Ti is given by Ai (Ti ) = Ri + Mi Bi . The rent and buy costs also
partition the nodes of Ti into two sets:
Definition 2.2. The core Ci of tree Ti consists of r and all nodes spanned by bought edges—edges
carrying at least Mi flow—and the periphery contains all vertices outside Ci .
The core Ci forms a connected component of Ti , and if we condition on the nodes in Ci then the
rent-or-buy problem becomes easy: demands outside the core pay linear cost until they reach Ci , so they
should take the shortest path, whereas within Ci we pay a fixed cost per edge length, so the best strategy
is to follow the min spanning tree. The cost Ri is therefore at least the sum of shortest path distances to
Ci , while Bi is at least the weight of the MST of Ci .
In addition to the SSRoB approximation, we will also employ the light, approximate shortest-path
tree algorithm of Khuller et al. [25]:
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 355
A SHISH G OEL AND I AN P OST
Definition 2.3 ([25]). For α ≥ 1 and β ≥ 1, an (α, β )-light, approximate shortest-path or (α, β )-LAST
is a spanning tree T of G with root r such that
• for each vertex v, the distance from v to r in T is at most α times the shortest path distance from v
to r in G, and
• the edge weight of T is at most β times the weight of an MST of G.
Khuller et al. show how to construct an (α, β )-LAST for any α > 1 and β ≥ (α + 1)/(α − 1).
Roughly, the algorithm performs a depth-first traversal of the MST of G starting from r, checking the
stretch of the shortest path to each node. If the path to some v has blown up by at least an α factor, then it
updates the tree to take the shortest path from v to r, adjusting other tree edges and distances accordingly.
See the paper [25] for a full description and analysis.
Finally, we define four parameters α, β , γ, and δ used by our algorithm whose values we will
optimize at the end:
• α > 1 is the approximation ratio for shortest paths used in our LAST,
• β ≥ (α + 1)/(α − 1) is the corresponding approximation to the MST in the LAST,
• γ > 1 is the factor by which we require normalized buy costs Bi to drop as i increases, moving
inward layer by layer in our tree, and
• δ > 1 is the factor by which rent costs Ri grow as i increases from layer to layer in our tree.
We now turn to a more thorough explanation of tree layers.
3 Tree layers
In the normal SSBaB problem when f (x) is given, the cost function is defined as f (x) = min j {σ j + δ j x},
the cheapest of a collection of different “pipes” or “cables” given to the algorithm, each with an affine
cost function σ j + δ j x. It is common (e. g., [17, 18, 21]) to first prune these pipes to a smaller set with
geometrically decreasing δ j ’s and geometrically increasing σ j ’s and then build a solution in layers where
each layer routes with a different pipe.
We perform an analogous procedure. We would like to build our simultaneous tree T in a series of
nested layers defined by the cores Ci of each tree Ti , so that the core of T under Ai is similar to Ci , but we
have no guarantees on the relationships between different cores: Ci and Ck may be entirely disjoint except
for r. However, we will show that as long as normalized buy costs Bi and Bk are within a constant factor
of each other, the same core can be used for both trees. Consequently, we are able to define nested layers
by choosing one Ci for each order of magnitude of Bi .
After finding λ -approximate trees Ti for each Ai , we loop through the costs Bi and Ri , discarding i
whenever Bi does not drop by γ or Ri does not grow by δ . We are left with a subset L of the Ti where the
Bi ’s are dropping by a factor of γ and the Ri ’s are growing by a factor of δ . The cores Ci for each i ∈ L
will define the layers of our tree. Algorithm 1 describes the procedure in more detail.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 356
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
Algorithm 1: Finding tree layers
Input: Graph G and demands D
Output: Set L and cores Ci for each i ∈ L
1 for i ← 0 to K do
2 Ti ← λ -approximate tree for Ai (x)
3 for i ← 1 to K do
4 if Ai (Ti−1 ) < Ai (Ti ) then Ti ← Ti−1
5 for i ← K − 1 down to 0 do
6 if Ai (Ti+1 ) < Ai (Ti ) then Ti ← Ti+1
7 for i ← 0 to K do
8 calculate Ci , Bi , Ri
9 LB ← 0
/
10 B ← ∞
11 for i ← 0 to K do
12 if Bi < 1γ B then
13 LB ← LB ∪ {i}
14 B ← Bi
15 L ← 0
/
16 R ← ∞
17 foreach i ∈ LB in decreasing order do
18 if Ri < δ1 R then
19 L ← L ∪ {i}
20 R ← Ri
21 return L and Ci for each i ∈ L
Intuitively, as it becomes more expensive to buy edges the optimum will buy fewer edges and
rent more. In the case of approximations, the progression becomes muddled because for some i the
approximation guarantee may be tight, while for i + 1 we may get lucky and find the optimum, resulting
in both rent and normalized buy costs dropping. We first show that the monotonicity in buy and rent costs
still holds as long as each Ti is better for Ai than both Ti−1 and Ti+1 .
Lemma 3.1. After line 8 of Algorithm 1, for every i we have Bi ≥ Bi+1 and Ri ≤ Ri+1 .
Proof. First we show that for each i, Ai (Ti ) ≤ min{Ai (Ti+1 ), Ai (Ti−1 )}. After the loop on lines 3–4 we
have Ai (Ti ) ≤ Ai (Ti−1 ), and after the second loop on lines 5–6 we have Ai (Ti ) ≤ Ai (Ti+1 ), so we only need
to show that the second loop does not break the first condition. If the second loop updates Ti , then Ai (Ti )
will only shrink, and if it changes Ti−1 it does this by setting Ti−1 ← Ti , which preserves Ai (Ti ) ≤ Ai (Ti−1 ).
Now consider Ai (Tk ) for any k. By definition Ai (x) ≤ x and Ai (x) ≤ Mi , so to upper bound Ai (Tk ) we
may assume edges within Ck pay Mi per unit length, which sums to Mi Bk , and edges outside Ck pay linear
cost, or Rk total, implying Ai (Tk ) ≤ Rk + Mi Bk . Therefore
Ri + Mi Bi = Ai (Ti ) ≤ Ai (Ti+1 ) ≤ Ri+1 + Mi Bi+1 =⇒ Mi (Bi − Bi+1 ) ≤ Ri+1 − Ri .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 357
A SHISH G OEL AND I AN P OST
Similarly,
Ri+1 + Mi+1 Bi+1 = Ai+1 (Ti+1 ) ≤ Ai+1 (Ti ) ≤ Ri + Mi+1 Bi =⇒ Ri+1 − Ri ≤ Mi+1 (Bi − Bi+1 ) .
Combining the inequalities,
Mi (Bi − Bi+1 ) ≤ Ri+1 − Ri ≤ Mi+1 (Bi − Bi+1 ) .
If Bi − Bi+1 < 0 the inequality is false because Mi+1 > Mi , so we conclude Bi ≥ Bi+1 . And using the first
inequality, 0 ≤ Mi (Bi − Bi+1 ) ≤ Ri+1 − Ri , so Ri ≤ Ri+1 .
We need to show that we can restrict our attention to Ti for i ∈ L. Suppose i < k but Bi ≤ γBk . Using
Lemma 3.1, observe that
Ak (Ti ) ≤ Ri + Mk Bi ≤ Rk + γMk Bk ≤ γAk (Tk ) .
Note this is independent of the size of the intersection of the cores Ci and Ck and any differences in
routing. The following lemma generalizes this simple but key observation and proves that approximating
each i ∈ L is sufficient.
Lemma 3.2. Suppose there exists a tree T and constants cB and cR such that for all i ∈ L there exists a
partition of the edges of T into two sets TBi and TRi satisfying
• A0 (TBi ) ≤ cB Bi and
• AK (TRi ) ≤ cR Ri ,
then for all k ∈ {0, . . . , K}, Ak (T ) ≤ max{cB γ, cR δ }λ Ak (Tk∗ ).
Proof. Let k ∈ {0, . . . , K}. Let j = max{ j ∈ LB | j ≤ k}. Either j = k, or k was discarded due to j on
lines 11–14 because Bk ≥ (1/γ)B j , and either way B j ≤ γBk . Now let i = min{i ∈ L | i ≥ j}. Again,
either i = j, or j was pruned due to i on lines 17–20, implying Ri ≤ δ R j (as well as i > k). Applying
Lemma 3.1 with i ≥ j and j ≤ k, we have Bi ≤ B j ≤ γBk and Ri ≤ δ R j ≤ δ Rk .
This is sufficient to bound the cost of Ak (T ):
Ak (T ) = Ak (TRi ) + Ak (TBi ) ≤ AK (TRi ) + Mk A0 (TBi )
≤ cR Ri + cB Mk Bi
≤ cR δ Rk + cB γMk Bk
≤ max{cR δ , cB γ}Ak (Tk ) ≤ max{cR δ , cB γ}λ Ak (Tk∗ ) .
The equality follows because TBi and TRi partition the edges of T . The first inequality holds because
AK (x) and Mk A0 (x) both upper bound Ak (x), the second is by assumption, the third is from the derivation
above, the fourth applies Ak (Tk ) = Rk + Mk Bk , and the last uses that Tk is a λ -approximation.
We will primarily assume that our SSRoB algorithm is a generic approximation, but Lemma 3.2 can
easily be improved to take advantage of an SSRoB algorithm with a stronger guarantee that separately
bounds Ri and Mi Bi in terms of the optimal costs R∗i and Mi B∗i as in [7].
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 358
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
Corollary 3.3. Let T , cB , and cR be as in Lemma 3.2, and suppose
• Ri ≤ µR R∗i + µB Mi B∗i and
• Mi Bi ≤ νR R∗i + νB Mi B∗i ,
then for all k, Ak (T ) ≤ max{cR δ µR + cB γνR , cR δ µB + cB γνB }Ak (Tk∗ ).
Proof. We change the inequalities in the proof above as follows:
Ak (T ) ≤ cR δ Rk + cB γMk Bk ≤ cR δ (µR R∗k + µB Mk B∗k ) + cB γ(νR R∗k + νB Mk B∗k )
≤ max{cR δ µR + cB γνR , cR δ µB + cB γνB }Ak (Tk∗ ) .
4 Constructing the tree
The construction of the tree itself is quite simple. We have a set of indices L and core sets Ci for i ∈ L.
Starting with the largest i ∈ L, i. e., smallest Bi , and working downward, we connect each Ci to T —the tree
so far—with a LAST. Algorithm 2 describes the procedure more formally. The notation G/T represents
contracting T to a single node in G, and G[Ci ] is the induced subgraph on Ci , so (G/T )[Ci ] denotes first
contracting T and then restricting to nodes in Ci .
Algorithm 2: Constructing the tree
Input: Graph G, set L, and accompanying Ci for each i ∈ L
Output: Aggregation tree T
1 T ← {r}
2 foreach i ∈ L in decreasing order do
3 T 0 ← (α, β )-LAST of (G/T )[Ci ] with root T
4 T ← T ∪T0
5 return T
Lemma 4.1. The graph T constructed by Algorithm 2 is a tree and spans all demand nodes.
Proof. Observe that 0 ∈ L, and R0 = 0, so C0 covers all demands. Therefore after the last iteration T
spans D. Each iteration only adds edges spanning new vertices, so no cycles are created.
The tree may contain paths connecting Steiner nodes that carry no flow. Such edges can be safely
pruned or just ignored because they contribute nothing to the cost.
All that remains is to define the partitions TBi and TRi and prove the bounds needed in Lemma 3.2. The
set TBi contains all edges present in T after connecting Ci , and TRi contains the rest. Both cost bounds will
follow easily from the geometrically changing costs: the cost A0 (TBi ) is dominated by the cost of the Ci
layer, an approximate MST, and AK (TRi ) is dominated by the rent costs of the next layer, an approximate
shortest-path tree. First, we bound the normalized buy cost of TBi .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 359
A SHISH G OEL AND I AN P OST
Lemma 4.2. Let i ∈ L, and TBi be the tree constructed by Algorithm 2 after the round when Ci is added.
Then the edge cost A0 (TBi ) is at most
βγ
Bi .
γ −1
Proof. We will prove by decreasing induction on i, i. e., the order in which the layers are built, that
A0 (TBi ) ≤ cBi for some c to be determined below. The base case corresponds to the first tree layer, which
is indexed by the largest i in L, or, equivalently, the smallest i such that Bi = 0. In this case, Ci = {r},
TBi = {r}, and the edge cost is 0.
Now let i ∈ L, k = min{k ∈ L | k > i} be the previous (inner) layer, and suppose the edge cost of TBk
is at most cBk . By the construction of L, we know Bk < (1/γ)Bi , implying TBk costs at most (c/γ)Bi . The
cost of an MST of Ci in G is at most Bi , and TBk may already span part of Ci , so connecting the rest with
an MST2 of (G/TBk )[Ci ] costs at most Bi . Using an (α, β )-LAST scales the cost by at most β .
The total cost of edges laid so far is at most (c/γ)Bi + β Bi , so the proof is complete as long as
cBi ≥ (c/γ)Bi + β Bi . Set c = β γ/(γ − 1); then we conclude that
c 1 βγ
c ≥ β + ⇐⇒ c 1 − ≥ β ⇐⇒ c ≥ .
γ γ γ −1
Now we bound the rent costs of TRi by a similar proof.
Lemma 4.3. Let i ∈ L, T be the final tree output by Algorithm 2, and TRi = T /TBi , i. e., all edges outside
of TBi . Then the rent cost AK (TRi ) is at most
αδ
Ri .
δ −α −1
Proof. We prove by increasing induction on i ∈ L (the reverse of Lemma 4.2) that AK (TRi ) ≤ cRi for
some c to be determined. Since 0 ∈ L, and TB0 covers everything, the base case TR0 costs 0 too.
For the inductive case, let i ∈ L, k = max{k ∈ L | k < i} be the next (outer) layer, and TRk have rent
cost at most cRk under AK . As before, note Rk < (1/δ )Ri , so AK (TRk ) ≤ (c/δ )Ri . Tree TBi spans Ci and
possibly more, so if all demands outside TBi take the shortest path from their sources to TBi , then the
shortest-path cost is at most Ri . However, consider the path taken through T from a source node s to TBi .
The node where the path transitions from edges of TRk to TBk may actually be farther away from TBi than s
is. But by the triangle inequality, the cost of sending all demands from the point they leave TRk to TBi via
shortest paths is at most (c/δ )Ri + Ri , the cost of sending all flow in TRk back to its source and from there
to TBi using shortest paths. The LAST algorithm guarantees α-approximate shortest paths, multiplying
the cost by α.
Consequently, the total rent cost for TRi is bounded by (c/δ )Ri + α ((c/δ )Ri + Ri ), which needs to be
at most cRi . Set c = αδ /(δ − α − 1); then we conclude that
c cα 1 α δ −α −1 αδ
c≥ + + α ⇐⇒ c 1 − − =c ≥ α ⇐⇒ c ≥ .
δ δ δ δ δ δ −α −1
2 We could allow Steiner nodes and use a Steiner tree approximation, but this would not improve the worst-case bound.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 360
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
We note that Lemma 4.3 explains how we circumvent a major obstacle to an O(1)-simultaneous
approximation—the Ω(log n) distortion lower bound for embedding arbitrary metrics into tree metrics [4].
If we needed to maintain distances between many pairs of nodes the task would be hopeless, but
Lemma 4.3 shows that it suffices to preserve the distance of each node to the next layer, so the graph of
distances to be maintained forms a tree.
We can now complete the proof of our main theorem and choose the optimal parameters.
√
Theorem 4.4. The tree T achieves a simultaneous approximation ratio of (1 + ε)λ (8 + 4 5) using a
λ -approximation to SSRoB. In particular,
• there is a randomized polynomial time algorithm that finds a 47.45 simultaneous approximation
with high probability,
• there is a deterministic polynomial time algorithm that finds a 55.58 simultaneous approximation,
and
• there exists a tree that is a 16.95 simultaneous approximation.
Proof. Applying Lemma 3.2 with cB = β γ/(γ − 1) (Lemma 4.2) and cR = αδ /(δ − α − 1) (Lemma 4.3),
the final approximation ratio for an arbitrary cost function f is
β γ2 αδ 2
(1 + ε)λ max , . (4.1)
γ −1 δ −α −1
where the extra 1 + ε comes from the approximation of f by a combination of Ai ’s. Now it is a simple
matter of applying calculus to find the optimal values for α, β , γ, and δ .
The easiest parameters to fix are γ and δ . For γ:
d β γ2 (2γ)(γ − 1) − γ 2
=β = 0 =⇒ γ(γ − 2) = 0 =⇒ γ = 2 .
dγ γ − 1 (γ − 1)2
For δ :
αδ 2 2δ (δ − α − 1) − δ 2
d
=α =0 =⇒ δ 2 − 2αδ − 2δ = δ (δ − 2α − 2) = 0
dδ δ − α − 1 (δ − α − 1)2
=⇒ δ = 2α + 2 .
Plugging γ = 2 and δ = 2α + 2 into (4.1), β γ 2 /(γ − 1) = 4β and
αδ 2 α(2α + 2)2
= = 4α(α + 1)
δ − α − 1 (2α + 2) − α − 1
so (4.1) is now max{4β , 4α(α + 1)}. The constraints on α and β require β ≥ (α + 1)/(α − 1) [25], so
one term blows up if the other shrinks. To minimize the maximum set the two expressions to be equal:
√
α +1 2 1± 5
β= = α(α + 1) =⇒ α(α − 1) = 1 =⇒ α − α − 1 = 0 =⇒ α = .
α −1 2
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 361
A SHISH G OEL AND I AN P OST
√
1+ 5
Using α = , we get
2
√ √ √ √
α +1 3+ 5 (3 + 5)(1 + 5) 8 + 4 5 √
β= = √ = = = 2+ 5
α − 1 −1 + 5 4 4
√
and δ = 2α + 2 = 3 + 5.
Summarizing, we set
√
1+ 5 √ √
α= , β = 2+ 5, γ = 2, and δ = 3+ 5,
2
for which
β γ2 αδ 2 √
= = 4(2 + 5) ,
γ −1 δ −α −1
√
so the simultaneous approximation ratio is (1 + ε)λ (8 + 4 5). The final ratio depends on the type of
algorithm desired:
• Using the best randomized approximation λ = 2.8, and the ratio is 47.45 with high probability.
• Using the best deterministic approximation λ = 3.28, and the ratio is 55.58.
• If the algorithm is allowed to run in exponential time λ = 1, and the ratio is 16.95.
The 2.8-approximation of Eisenbrand et al. [7] actually provides a slightly stronger guarantee on Ri
and Bi , and we can use Corollary 3.3 to get a tiny improvement in the approximation ratio at the cost of a
more complex derivation:
Theorem 4.5. There is a randomized polynomial time algorithm that finds a 47.07 simultaneous approxi-
mation with high probability.
Proof. Lemma 2 and Theorem 5 in [7] prove that
.807
E[Ri ] ≤ 2R∗i + Mi B∗i and E[Mi Bi ] ≤ ρ(x + ε)R∗i + ρMi B∗i ,
x
where ρ = 1.39 is the Steiner tree approximation ratio and x ∈ (0, 1] is a parameter. Applying Corollary 3.3
with
.807
µR = 2 , µB = , νR = ρ(x + ε) , and νB = ρ ,
x
the simultaneous ratio is bounded by
2αδ 2 ρ(x + ε)β γ 2 .807αδ 2 ρβ γ 2
(1 + ε) max + , + . (4.2)
δ −α −1 γ −1 x(δ − α − 1) γ − 1
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 362
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
For γ and δ , both expressions inside the max function are minimized exactly as above in Theorem 4.4
with γ = 2 and δ = 2α + 2. Also as in Theorem 4.4, β can be set to α+1α−1 , the minimum allowed by the
constraints. Plugging in these values and simplifying, expression (4.2) becomes
ρ(x + ε) .807α ρ
4(α + 1) max 2α + , + .
α −1 x α −1
Set the two expressions inside the maximization to be equal, and solve the resulting quadratic equation in
x to get (for ε = 0):
s
1 α(α − 1) α 2 (α − 1)2 .193α(α − 1) 1
x= − + − +
2 ρ ρ2 ρ 4
using that x > 0.
The problem is now to minimize
s
ρ2
ρx 2ρ(α + 1) .193ρα
4(α + 1) 2α + = 4α(α + 1) + + 4(α + 1) α 2 − + .
α −1 α −1 α −1 (α − 1)2
This expression is unwieldy to optimize analytically, but when ρ = 1.39 it achieves a minimum of about
47.068 for α ≈ 1.5495 (which makes x ≈ .5995). For ε sufficiently small this gives a bound of 47.07
with high probability.
We leave as an open question the problem of exploiting Corollary 3.3 to substantially improve the
ratio.
4.1 Runtime
Let tRoB (n, m) be the running time of our SSRoB approximation on a graph with n vertices and m
edges, which must be at least Ω(n) to write down the output. When ε is constant, running the SSRoB
approximation for each i takes O(tRoB (n, m) log D) time, or O(tRoB (n, m) log D log log D) for a randomized
algorithm. Subsequent loops in Algorithm 1 take O(n log D).
For each of the O(log D) iterations of Algorithm 2 we need to do a graph contraction and run the
LAST algorithm, which requires computing the MST and shortest path trees, so the runtime is O((m + n +
tSP (n, m) +tMST (n, m)) log D), where tSP (n, m) and tMST (n, m) denote the runtimes of the shortest path and
MST algorithms used. Using Dijkstra’s algorithm, tSP (n, m) = O(m + n log n) [11], which dominates the
other steps in the loop. Combining the two algorithms, the total time is O((tRoB (n, m) + m + n log n) log D)
for deterministic SSRoB algorithms and O((tRoB (n, m) log log D + m + n log n) log D) for randomized
ones.
5 Remarks on the approximation ratio for SSRoB
The current-best algorithm for SSRoB [7] depends on the approximation ratio for Steiner tree, which has
recently been reduced to 1.39 [6]. The improved SSRoB ratio does not currently appear in the literature,
so we include the calculation for completeness. See the original paper for details.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 363
A SHISH G OEL AND I AN P OST
Theorem 5.1 ([7, 6]). There is a 2.8-approximation for SSRoB.
Proof. By the proof of Theorem 6 in [7], there is an SSRoB algorithm with expected cost
MB∗
ρ(MB∗ + (x + ε)R∗ ) + 2R∗ + 0.807
x
where ρ is the approximation ratio for Steiner tree and x is a parameter in (0, 1]. Set the coefficients of R∗
and MB∗ to be equal and solve the resulting quadratic equation in x. For ρ = 1.39, choosing x = .5735
gives an approximation ratio of 2.80.
6 Open problems
We have answered the open questions posed by Goel and Estrin [12] and Goel and Post [13], but there are
several avenues for further work. Our simultaneous ratio of 47.45 already improves upon many algorithms
for normal SSBaB and is only a factor of 2.33 away from the best. It would be nice to eliminate this
gap or, alternately, prove that a gap exists between the approximation achievable for fixed f and the best
simultaneous ratio. We know of no lower bounds on what simultaneous ratio may be possible, so any
progress in this direction would also be interesting. Generalizing the settings in which O(1) simultaneous
ratios are possible would be interesting, but may be unlikely given that one must contend with lower
bounds for metric tree embedding [4] and multi-sink buy-at-bulk [1].
Acknowledgements
We thank the anonymous conference and journal reviewers for many helpful comments that improved the
presentation and for suggesting Corollary 3.3 and Theorem 4.5.
References
[1] M ATTHEW A NDREWS: Hardness of buy-at-bulk network design. In Proc. 45th FOCS, pp. 115–124.
IEEE Comp. Soc. Press, 2004. [doi:10.1109/FOCS.2004.32] 364
[2] M ATTHEW A NDREWS AND L ISA Z HANG: The access network design problem. In Proc. 39th
FOCS, pp. 40–49. IEEE Comp. Soc. Press, 1998. [doi:10.1109/SFCS.1998.743427] 352
[3] BARUCH AWERBUCH AND YOSSI A ZAR: Buy-at-bulk network design. In Proc. 38th FOCS, pp.
542–547. IEEE Comp. Soc. Press, 1997. [doi:10.1109/SFCS.1997.646143] 354
[4] YAIR BARTAL: Probabilistic approximation of metric spaces and its algorithmic applications. In
Proc. 37th FOCS, pp. 184–193. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548477]
354, 361, 364
[5] YAIR BARTAL: On approximating arbitrary metrics by tree metrics. In Proc. 30th STOC, pp.
161–168. ACM Press, 1998. [doi:10.1145/276698.276725] 354
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 364
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
[6] JAROSLAW B YRKA , FABRIZIO G RANDONI , T HOMAS ROTHVOSS , AND L AURA S ANITÀ: An
improved LP-based approximation for Steiner tree. In Proc. 42nd STOC, pp. 583–592. ACM Press,
2010. [doi:10.1145/1806689.1806769] 354, 355, 363, 364
[7] F RIEDRICH E ISENBRAND , FABRIZIO G RANDONI , T HOMAS ROTHVOSS , AND G UIDO S CHÄFER:
Connected facility location via random facility sampling and core detouring. J. Comput. System
Sci., 76(8):709–726, 2010. [doi:10.1016/j.jcss.2010.02.001] 352, 354, 355, 358, 362, 363, 364
[8] M IHAELA E NACHESCU , A SHISH G OEL , R AMESH G OVINDAN , AND R AJEEV M OTWANI: Scale-
free aggregation in sensor networks. Theoret. Comput. Sci., 344(1):15–29, 2005. Preliminary
version in ALGOSENSORS’04. [doi:10.1016/j.tcs.2005.06.023] 354
[9] M ATTHIAS E NGLERT AND H ARALD R ÄCKE: Oblivious routing for the L p -norm. In Proc. 50th
FOCS, pp. 32–40. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.52] 354
[10] J ITTAT FAKCHAROENPHOL , S ATISH R AO , AND K UNAL TALWAR: A tight bound on approximating
arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004. Preliminary version
in STOC’03. [doi:10.1016/j.jcss.2004.04.011] 353, 354
[11] M ICHAEL L. F REDMAN AND ROBERT E NDRE TARJAN: Fibonacci heaps and their uses in improved
network optimization algorithms. J. ACM, 34:596–615, 1987. Preliminary version in FOCS’84.
[doi:10.1145/28869.28874] 363
[12] A SHISH G OEL AND D EBORAH E STRIN: Simultaneous optimization for concave costs: single sink
aggregation or single source buy-at-bulk. Algorithmica, 43(1):5–15, 2005. Preliminary version in
SODA’03. [doi:10.1007/s00453-005-1155-0] 353, 354, 364
[13] A SHISH G OEL AND I AN P OST: An oblivious O(1)-approximation for single source buy-at-bulk. In
Proc. 50th FOCS, pp. 442–450. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.41] 353,
364
[14] A SHISH G OEL AND I AN P OST: One tree suffices: A simultaneous O(1)-approximation for
single-sink buy-at-bulk. In Proc. 51st FOCS, pp. 593–600. IEEE Comp. Soc. Press, 2010.
[doi:10.1109/FOCS.2010.62] 353
[15] FABRIZIO G RANDONI AND G IUSEPPE F. I TALIANO: Improved approximation for single-sink
buy-at-bulk. In 17th Int. Symp. on Algorithms and Computation (ISAAC’06), volume 4288, pp.
111–120. Springer, 2006. [doi:10.1007/11940128_13] 354
[16] FABRIZIO G RANDONI AND T HOMAS ROTHVOSS: Network design via core detouring for prob-
lems without a core. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming
(ICALP’10), pp. 490–502. Springer, 2010. [doi:10.1007/978-3-642-14165-2_42] 352, 353, 354
[17] S UDIPTO G UHA , A DAM M EYERSON , AND K AMESH M UNAGALA: A constant factor approxima-
tion for the single sink edge installation problems. In Proc. 33rd STOC, pp. 383–388. ACM Press,
2001. [doi:10.1145/380752.380827] 352, 354, 356
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 365
A SHISH G OEL AND I AN P OST
[18] S UDIPTO G UHA , A DAM M EYERSON , AND K AMESH M UNAGALA: A constant factor approxi-
mation for the single sink edge installation problem. SIAM J. Comput., 38(6):2426–2442, 2010.
[doi:10.1137/050643635] 352, 354, 356
[19] A NUPAM G UPTA , M OHAMMAD T. H AJIAGHAYI , AND H ARALD R ÄCKE: Oblivious network
design. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 970–979.
ACM Press, 2006. [doi:10.1145/1109557.1109665] 354
[20] A NUPAM G UPTA , J ON K LEINBERG , A MIT K UMAR , R AJEEV R ASTOGI , AND B ULENT Y ENER:
Provisioning a virtual private network: A network design problem for multicommodity flow. In
Proc. 33rd STOC, pp. 389–398. ACM Press, 2001. [doi:10.1145/380752.380830] 354
[21] A NUPAM G UPTA , A MIT K UMAR , M ARTIN P ÁL , AND T IM ROUGHGARDEN: Approximation via
cost sharing: Simpler and better approximation algorithms for network design. J. ACM, 54(3):1–38,
2007. [doi:10.1145/1236457.1236458] 354, 356
[22] A NUPAM G UPTA , A RAVIND S RINIVASAN , AND É VA TARDOS: Cost-sharing mechanisms
for network design. Algorithmica, 50(1):98–119, 2008. Preliminary version in APPROX’04.
[doi:10.1007/s00453-007-9065-y] 354
[23] R AJA J OTHI AND BALAJI R AGHAVACHARI: Improved approximation algorithms for the single-sink
buy-at-bulk network design problems. J. Discrete Algorithms, 7(2):249–255, 2009. Preliminary
version in SWAT’04. [doi:10.1016/j.jda.2008.12.003] 354
[24] DAVID R. K ARGER AND M ARIA M INKOFF: Building Steiner trees with incomplete
global knowledge. In Proc. 41st FOCS, pp. 613–623. IEEE Comp. Soc. Press, 2000.
[doi:10.1109/SFCS.2000.892329] 352, 354
[25] S. K HULLER , B. R AGHAVACHARI , AND N. YOUNG: Balancing minimum spanning trees and
shortest-path trees. Algorithmica, 14(4):305–321, 1995. [doi:10.1007/BF01294129] 353, 354, 355,
356, 361
[26] B HASKAR K RISHNAMACHARI , D EBORAH E STRIN , AND S TEPHEN W ICKER: Modelling data-
centric routing in wireless sensor networks. Technical Report CENG 02-14, Univ. Southern Calif.
Dept. EE - Systems (18 pp), 2002. PDF. 352
[27] Y. R ABINOVICH AND R. R AZ: Lower bounds on the distortion of embedding finite metric spaces
in graphs. Discrete Comput. Geom., 19(1):79–94, 1998. [doi:10.1007/PL00009336] 353
[28] R. R AVI AND F. S. S ALMAN: Approximation algorithms for the traveling purchaser problem and
its variants in network design. In Proc. 7th Ann. European Symp. on Algorithms (ESA’99), pp.
696–696. Springer, 1999. [doi:10.1007/3-540-48481-7_4] 354
[29] F. S. S ALMAN , J. C HERIYAN , R. R AVI , AND S. S UBRAMANIAN: Buy-at-bulk network design:
Approximating the single-sink edge installation problem. In Proc. 8th Ann. ACM-SIAM Symp. on
Discrete Algorithms (SODA’97), pp. 619–628. ACM Press, 1997. [ACM:314397] 352, 354
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 366
O NE T REE S UFFICES : A S IMULTANEOUS O(1)-A PPROXIMATION FOR S INGLE -S INK B UY- AT-B ULK
[30] F. S. S ALMAN , J. C HERIYAN , R. R AVI , AND S. S UBRAMANIAN: Approximating the single-
sink link-installation problem in network design. SIAM J. Optim., 11(3):595–610, 2001.
[doi:10.1137/S1052623497321432] 352, 354
[31] C HAITANYA S WAMY AND A MIT K UMAR: Primal-dual algorithms for connected facility lo-
cation problems. Algorithmica, 40(4):245–269, 2004. Preliminary version in APPROX’02.
[doi:10.1007/s00453-004-1112-3] 354
[32] K UNAL TALWAR: The single-sink buy-at-bulk LP has constant integrality gap. In Proc. 9th Ann.
Conf. on Integer Programming and Combinatorial Optimization (IPCO ’02), pp. 475–486. Springer,
2002. [doi:10.1007/3-540-47867-1_33] 354
[33] A NKE VAN Z UYLEN: Deterministic sampling algorithms for network design. Algorithmica,
60(1):110–151, 2011. Preliminary version in ESA’08. [doi:10.1007/s00453-009-9344-x] 354
[34] DAVID P. W ILLIAMSON AND A NKE VAN Z UYLEN: A simpler and better derandomization of
an approximation algorithm for single source rent-or-buy. Oper. Res. Lett., 35(6):702–712, 2007.
[doi:10.1016/j.orl.2007.02.005] 354, 355
AUTHORS
Ashish Goel
Associate Professor
Stanford University
ashishg stanford edu
http://www.stanford.edu/~ashishg/
Ian Post
graduate student
Stanford University
itp stanford edu
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 367
A SHISH G OEL AND I AN P OST
ABOUT THE AUTHORS
A SHISH G OEL is an Associate Professor of Management Science and Engineering and (by
courtesy) Computer Science at Stanford University, and a member of Stanford’s Institute
for Computational and Mathematical Engineering. He received his Ph. D. in Computer
Science from Stanford in 1999, advised by Serge Plotkin, and was an Assistant Professor
of Computer Science at the University of Southern California from 1999 to 2002. His
research interests lie in the design, analysis, and applications of algorithms; current
application areas of interest include social networks, Internet commerce, and large scale
data processing. Ashish is a recipient of an Alfred P. Sloan faculty fellowship (2004-06),
a Terman faculty fellowship from Stanford, an NSF Career Award (2002-07), and a
Rajeev Motwani mentorship award (2010). He was a co-author on the paper that won the
best paper award at WWW 2009. Ashish currently holds the 3COM faculty fellowship in
Stanford’s School of Engineering, and serves on the technical advisory board of Twitter,
Inc.
I AN P OST is a graduate student at Stanford advised by Ashish Goel. His research interests
are in algorithms.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 351–368 368