One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk
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 …