pdf icon
Volume 8 (2012) Article 15 pp. 351-368
Special Issue in Honor of Rajeev Motwani
One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk
Received: September 14, 2010
Published: July 20, 2012
Download article from ToC site:
[PDF (248K)]    [PS (906K)]    [PS.GZ (265K)]
[Source ZIP]
Keywords: network design, buy-at-bulk, simultaneous optimization
ACM Classification: F.2.2, G.2.2
AMS Classification: 68W25, 68R10

Abstract: [Plain Text Version]

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.