Online Buy-at-Bulk Network Design
Conference Paper
We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show:1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs.2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs.3. For any fixed ∈ > 0, a polynomial time online algorithm with a competitive ratio of O(k{1/2+∈} polylog(n)) (where k is the number of demands) for MC-BB in directed graphs.4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine - an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.
Full Text
Duke Authors
Cited Authors
- Ene, A; Chakrabarty, D; Krishnaswamy, R; Panigrahi, D
Published Date
- December 11, 2015
Published In
Volume / Issue
- 2015-December /
Start / End Page
- 545 - 562
International Standard Serial Number (ISSN)
- 0272-5428
International Standard Book Number 13 (ISBN-13)
- 9781467381918
Digital Object Identifier (DOI)
- 10.1109/FOCS.2015.40
Citation Source
- Scopus