TY - GEN
T1 - LAST but not least
T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
AU - Gupta, Anupam
AU - Ravi, R.
AU - Talwar, Kunal
AU - Umboh, Seeun William
N1 - Publisher Copyright:
Copyright © by SIAM.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85016181944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85016181944&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974782.38
DO - 10.1137/1.9781611974782.38
M3 - Conference contribution
AN - SCOPUS:85016181944
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 589
EP - 599
BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
A2 - Klein, Philip N.
PB - Association for Computing Machinery
Y2 - 16 January 2017 through 19 January 2017
ER -