Theory of Computing
-------------------
Title     : One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk
Authors   : Ashish Goel and Ian Post
Volume    : 8
Number    : 15
Pages     : 351-368
URL       : https://theoryofcomputing.org/articles/v008a015

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.