Computer Science – Data Structures and Algorithms
Scientific paper
2010-04-13
Computer Science
Data Structures and Algorithms
16 pages. To appear in FOCS 2010. Version 2 incorporates reviewer feedback and has updated references. The approximation ratio
Scientific paper
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 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.
Goel Ashish
Post Ian
No associations
LandOfFree
One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-524855