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.

通过使用 “部分树度量”，我们将有限的跳限制问题转化为在树上的无限制跳问题，并且给了许多经典网络设计问题的第一个多对数双标准逼近。这些问题包括斯特纳森林、组斯特纳树、组斯特纳森林、大宗购买网络设计以及在线和迭代多个问题。