Tree embeddings for hop-constrained network design
Tree embeddings for hop-constrained network design
复制标题
用于跳数受限网络设计的树嵌入
DOI：
10.1145/3406325.3451053
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zuzic, Goran
中科院分区：
文献类型：
--
作者：
Haeupler, Bernhard;Hershkowitz, D. Ellis;Zuzic, Goran
网络设计问题旨在计算低成本结构，例如路线、树和子图。通常，要求这些结构具有较小的啤酒花长度或啤酒花直径是自然且可取的。不幸的是，有跳数约束的优化问题比无跳数约束的优化问题要困难得多，也不太容易理解。在这种情况下，一个重要的算法障碍是图中的跳数约束距离远不是一个度量。尽管如此，我们表明，跳数约束距离可以通过“部分树度量”上的分布来近似。我们将此结果构建成一个强大且通用的算法工具，与经典的概率树嵌入类似，将一般图中的跳数约束问题减少到 树上的跳跃无约束问题。然后，我们使用该工具为许多经典网络设计问题的跳数约束变体给出第一个多对数双标准近似。其中包括斯坦纳森林、斯坦纳树组、斯坦纳森林组、批量购买网络设计以及许多这些问题的在线和遗忘版本。
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.
登录
查看更多内容
次多项式时间内的动态低拉伸生成树
DOI：
--
发表时间：
2020
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. Chechik;Tianyi Zhang
通讯作者：
Tianyi Zhang
用于设计直径约束最小跨度树和斯坦纳树的网络流模型
影响因子：
2.1
作者：
Luís Gouveia;T. Magnanti
通讯作者：
T. Magnanti
基本 k-Spanner 问题的强不可逼近性
DOI：
--
发表时间：
2000
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Michael Elkin;D. Peleg
通讯作者：
D. Peleg
跳数受限的分配网络配置问题的扩展公式
影响因子：
6.4
作者：
Jérôme De Boeck;B. Fortz
通讯作者：
B. Fortz
可生存跳数受限连接设施位置问题的 IP 建模
DOI：
--
发表时间：
2013
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
A. Bley;S. M. Hashemi;M. Rezapour
通讯作者：
M. Rezapour