论文标题
树木嵌入式网络设计的嵌入
Tree Embeddings for Hop-Constrained Network Design
论文作者
论文摘要
网络设计问题旨在计算低成本结构，例如路线，树木和子图。通常，自然而然地要求这些结构的跳高长度或直径较小。不幸的是，与Hop限制的优化问题相比，与他们的啤酒花限制的同行相比，更难理解。在这种情况下，一个重要的算法障碍是，图表中的漏洞距离远非距离。 我们表明，在“部分树指标”上的分布中，可以近似地限制途径。我们将此结果构建为一种功能强大且多才多艺的算法工具，该工具与经典的概率树嵌入类似，将一般图中的啤酒花限制问题减少到树木上的无限问题。然后，我们使用此工具为许多经典网络设计问题的啤酒花限制变体提供了第一个聚合物两合一的近似值。其中包括Steiner Forest，Group Steiner Tree，Group Steiner Forest，Buy-At-atulk网络设计以及在线和许多此类问题的遗忘版本。
Network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less well understood than their hop-unconstrained counterparts. A significant algorithmic barrier in this setting is the fact that hop-constrained distances in graphs are very far from being a metric. We show that, nonetheless, hop-constrained distances can be approximated by distributions over "partial tree metrics." We build this result into a powerful and versatile algorithmic tool which, similarly to classic probabilistic tree embeddings, reduces hop-constrained problems in general graphs to hop-unconstrained problems on trees. We then use this tool to give the first poly-logarithmic bicriteria approximations for the hop-constrained variants of many classic network design problems. These include Steiner forest, group Steiner tree, group Steiner forest, buy-at-bulk network design as well as online and oblivious versions of many of these problems.
