Published: July 20, 2012
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.
Licensed under a Creative Commons Attribution License (CC-BY)