## Online buy-at-bulk network design

We present the first online algorithms for the nonuniform, 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 (a) a polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs, (b) a quasi-polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs, (c) for any fixed > 0, a polynomial time online algorithm with a competitive ratio of Õk12 +) (where k is the number of demands, and the tilde hides polylog factors) for MC-BB in directed graphs, and (d) algorithms with matching competitive ratios for the prize-collecting variant of all the preceding problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs [B. Awerbuch and Y. Azar, FOCS, 1997, pp. 542–547], and a polylogarithmic-competitive algorithm was known for the edge-weighted single-sink problem [A. Meyerson, Procedings of SPAA, 2004, pp. 275–280]. We believe no online algorithm was known in the node-weighted and directed settings, even for uniform costs. Our main technical contribution is an online reduction theorem of MC-BB problems to their single-sink counterparts. We use the concept of Junction-tree solutions from [C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Proceedings of FOCS, 2006, pp. 677–686], which play an important role in solving the offline versions of the problem via a greedy subroutine—an inherently offline procedure. We use just the existence of good Junction-trees for our reduction.

### Duke Scholars

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics

### Citation

*SIAM Journal on Computing*,

*47*(4), 1505–1528. https://doi.org/10.1137/16M1117317

*SIAM Journal on Computing*47, no. 4 (January 1, 2018): 1505–28. https://doi.org/10.1137/16M1117317.

*SIAM Journal on Computing*, vol. 47, no. 4, Jan. 2018, pp. 1505–28.

*Scopus*, doi:10.1137/16M1117317.

## Published In

## DOI

## EISSN

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Computation Theory & Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics