LAST but not least: online spanners for buy-at-bulk

• DOI: 10.5555/3039686.3039724
• Publication Date: 2017-01-16
• Authors: Anupam Gupta; R. Ravi; Kunal Talwar; Seeun William Umboh
• Keywords: Competitive Analysis; Online algorithm; Steiner tree problem; Randomized Algorithm; Tree (set theory)

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