TechFest Workshop – Theory Day – Session 3

  • Ravishankar Krishnaswamy | MSR India

We present the first non-trivial online algorithms for the classical multi-commodity buy-at-bulk problem. The goal is to provision a low-cost network over time to support bandwidth demands that also arrive over time. Previously, online algorithms were known only for the special cases of all links having the same cost (Awerbuch and Azar, FOCS 1997), or when all demands share the same destination (Meyerson, SPAA 2004).. At the crux of our algorithm is a generic online reduction for a class of network design problems from multi-commodity demands to single-commodity instances. (Joint work with Deeparnab Chakrabarty, Alina Ene and Debmalya Panigrahi.)

Watch Next