  The online (uniform) buy-at-bulk network design problem asks us to design a
network, where the edge-costs exhibit economy-of-scale. Previous approaches to
this problem used tree- embeddings, giving us randomized algorithms. Moreover,
the optimal results with a logarithmic competitive ratio requires the metric on
which the network is being built to be known up-front; the competitive ratios
then depend on the size of this metric (which could be much larger than the
number of terminals that arrive).
  We consider the buy-at-bulk problem in the least restrictive model where the
metric is not known in advance, but revealed in parts along with the demand
points seeking connectivity arriving online. For the single sink buy-at-bulk
problem, we give a deterministic online algorithm with competitive ratio that
is logarithmic in k, the number of terminals that have arrived, matching the
lower bound known even for the online Steiner tree problem. In the oblivious
case when the buy-at-bulk function used to compute the edge-costs of the
network is not known in advance (but is the same across all edges), we give a
deterministic algorithm with competitive ratio polylogarithmic in k, the number
of terminals.
  At the heart of our algorithms are optimal constructions for online Light
Approximate Shortest-path Trees (LASTs) and spanners, and their variants. We
give constructions that have optimal trade-offs in terms of cost and stretch.
We also define and give constructions for a new notion of LASTs where the set
of roots (in addition to the points) expands over time. We expect these
techniques will find applications in other online network-design problems.
