An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk

Ashish Goel, Ian Post

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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 [10] 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|. © 2009 IEEE.
Original languageEnglish (US)
Title of host publication2009 50th Annual IEEE Symposium on Foundations of Computer Science
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages9
ISBN (Print)9781424451166
StatePublished - Oct 2009
Externally publishedYes


Dive into the research topics of 'An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk'. Together they form a unique fingerprint.

Cite this