Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We study the single-sink buy-at-bulk problem with an unknown cost function. We want 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, deterministic, 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 49.48-approximation of the optimal cost for that f. This is within a factor of 2 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.

Questions and Answers

You need to be logged in to be able to post here.