LAST but not Least: Online Spanners for Buy-at-Bulk
LAST but not Least: Online Spanners for Buy-at-Bulk
复制标题
最后但并非最不重要的一点：批量购买的在线扳手
DOI：
10.1137/1.9781611974782.38
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Umboh
中科院分区：
文献类型：
--
作者：
Anupam Gupta;R. Ravi;Kunal Talwar;S. Umboh
在线（统一）批量购买网络设计问题要求我们设计一个网络，其中边缘成本表现出规模经济。以前解决这个问题的方法使用树嵌入，为我们提供了随机算法。此外，具有对数竞争比的最佳结果需要预先了解构建网络所依据的指标；然后，竞争比率取决于该指标的大小（可能比到达的终端数量大得多）。我们在限制最少的模型中考虑批量购买问题，其中指标事先未知，但随着寻求在线连接的需求点一起部分显示。对于单汇批量购买问题，我们给出了一种确定性在线算法，其竞争比是 k 的对数（已到达的终端数量），与在线斯坦纳树问题已知的下限相匹配。在不经意的情况下，当用于计算网络边缘成本的批量购买函数事先未知（但在所有边缘上都相同）时，我们给出了一种确定性算法，其竞争比以 k（终端数量）为多对数。我们算法的核心是在线轻型近似最短路径树（LAST）和扳手及其变体的最佳构造。我们提供在成本和拉伸方面具有最佳权衡的结构。我们还定义并给出了 LAST 的新概念，其中根集（除了点之外）随着时间的推移而扩展。我们预计这些技术将在其他在线网络设计问题中得到应用。
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.