TY - GEN

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

AU - Goel, Ashish

AU - Post, Ian

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Research supported by an NSF ITR grant and the Stanford-KAUSTalliance for academic excellence.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2009/10

Y1 - 2009/10

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/597539

UR - http://ieeexplore.ieee.org/document/5438608/

UR - http://www.scopus.com/inward/record.url?scp=77952390567&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2009.41

DO - 10.1109/FOCS.2009.41

M3 - Conference contribution

SN - 9781424451166

SP - 442

EP - 450

BT - 2009 50th Annual IEEE Symposium on Foundations of Computer Science

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -