We consider the single-source (or single-sink) buy-at-bulk problem with an
unknown concave cost function. We want to route a set of demands along a graph
to or from a designated root node, and the cost of routing x units of flow
along an edge is proportional to some concave, non-decreasing function f such
that f(0) = 0. We present a polynomial time algorithm that finds a distribution
over trees such that the expected cost of a tree for any f is within an
O(1)-factor of the optimum cost for that f. The previous best simultaneous
approximation for this problem, even ignoring computation time, was O(log |D|),
where D is the multi-set of demand nodes.

We design a simple algorithmic framework using the ellipsoid method that
finds an O(1)-approximation if one exists, and then construct a separation
oracle using a novel adaptation of the Guha, Meyerson, and Munagala algorithm
for the single-sink buy-at-bulk problem that proves an O(1) approximation is
possible for all f. The number of trees in the support of the distribution
constructed by our algorithm is at most 1+log |D|.