06087407

j

06087407 Goel, Ashish Post, Ian One tree suffices: a simultaneous $O(1)$-approximation for single-sink buy-at-bulk. Theory Comput. 8, Paper No. 15, 351-368, electronic only (2012). 2012 The University of Chicago, Department of Computer Science, Chicago, IL EN network design buy-at-bulk simultaneous optimization

doi:10.4086/toc.2012.v008a002

Summary: 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.