Computer Science – Data Structures and Algorithms
Scientific paper
2009-08-26
Computer Science
Data Structures and Algorithms
22 pages, 1 figure To appear in the proceedings of the 50th annual IEEE Symposium on Foundations of Computer Science (FOCS 200
Scientific paper
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|.
Goel Ashish
Post Ian
No associations
LandOfFree
An Oblivious O(1)-Approximation for Single Source 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 An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-623830