Online Buy-at-Bulk Network Design
Online Buy-at-Bulk Network Design
复制标题
在线批量购买网络设计
DOI：
10.1109/focs.2015.40
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Debmalya Panigrahi
中科院分区：
文献类型：
--
作者：
Alina Ene;Deeparnab Chakrabarty;Ravishankar Krishnaswamy;Debmalya Panigrahi
我们提出了第一个非平凡的在线算法的非均匀，多商品批量购买（MC-BB）网络设计问题。我们的竞争比定性匹配最好的已知的近似因子为相应的离线问题。特别是，我们表明：1。无向边权图MC-BB问题的一个多项式时间在线算法.无向赋权图MC-BB问题的一个具有多对数竞争比的准多项式时间在线算法.对于任意固定的ε > 0，给出了有向图中MC-BB的竞争比为O <$（k{1/2+ε} polylog（n））（其中k为需求数）的多项式时间在线算法.所有上述问题的奖金收集变体的匹配竞争比算法。在我们的工作之前，对数竞争比已知的无向，边加权图只有在特殊情况下的均匀成本（Awerbuch和Azar，FOCS 1997），和多对数竞争比已知的边加权单汇问题（Meyerson，SPAA 2004）。据我们所知，没有以前的在线算法是已知的，即使是统一的成本，在节点加权和定向设置。上述结果的主要引擎是MC-BB问题到其单汇（SS-BB）对应问题的在线约化定理。我们使用连接树解决方案的概念（Chekuri等人，FOCS 2006），在通过贪婪子例程解决问题的离线版本中发挥了重要作用-一个固有的离线过程。我们的主要技术贡献是在设计一个在线算法，只使用良好的连接树的存在，以减少一个MC-BB实例到多个SS-BB子实例。沿着的方式，我们还给出了第一个非平凡的在线节点加权/定向单汇批量购买算法。除了新的结果，我们的通用减少也产生了新的证明，最近的结果为在线节点加权施泰纳森林和在线组施泰纳森林问题。
We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show:1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs.2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs.3. For any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of O̅(k{1/2+ε} polylog(n)) (where k is the number of demands) for MC-BB in directed graphs.4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.