论文标题
超越树木嵌入 - 截止日期或延迟的网络设计的确定性框架
Beyond Tree Embeddings -- a Deterministic Framework for Network Design with Deadlines or Delay
论文作者
论文摘要
我们考虑网络设计问题，截止日期或延迟。这些模型的所有先前结果均基于图形的随机嵌入到树中（HST），然后在该树上解决该问题。我们表明这不是必需的。特别是，我们为这些问题设计了一个确定性框架，而不是基于嵌入。这使我们能够提供确定性的$ \ text {poly-log}（n）$ - 施泰纳树的竞争算法，广义的施泰纳树，节点加权的施泰纳树，（非均匀）设施位置和带有截止日期或延迟的施泰纳树位置（$ n $ n $ n $是Nodes）。我们的确定性算法还可以改善与以前的一些随机结果相比的保证。此外，对于其中一些问题，我们还显示了$ \ text {poly-log}（n）$的下限，这意味着我们的框架是最佳的，符合多狗的力量。在这些问题的所有考虑中，我们的算法和技术与这些问题的算法和技术有很大差异。
We consider network design problems with deadline or delay. All previous results for these models are based on randomized embedding of the graph into a tree (HST) and then solving the problem on this tree. We show that this is not necessary. In particular, we design a deterministic framework for these problems which is not based on embedding. This enables us to provide deterministic $\text{poly-log}(n)$-competitive algorithms for Steiner tree, generalized Steiner tree, node weighted Steiner tree, (non-uniform) facility location and directed Steiner tree with deadlines or with delay (where $n$ is the number of nodes). Our deterministic algorithms also give improved guarantees over some previous randomized results. In addition, we show a lower bound of $\text{poly-log}(n)$ for some of these problems, which implies that our framework is optimal up to the power of the poly-log. Our algorithms and techniques differ significantly from those in all previous considerations of these problems.
