An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk
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 …