@inproceedings{chakrabarty2015online,
author = {Chakrabarty, Deeparnab and Ene, Alina and Krishnaswamy, Ravishankar and Panigrahi, Debmalya},
title = {Online Buy-at-Bulk Network Design},
booktitle = {FOCS '15 Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)},
year = {2015},
month = {October},
abstract = {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.},
publisher = {IEEE Computer Society Washington, DC, USA},
url = {http://approjects.co.za/?big=en-us/research/publication/online-buy-bulk-network-design/},
pages = {545-562},
isbn = {978-1-4673-8191-8},
edition = {FOCS '15 Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)},
}