Tree embeddings for hop-constrained network design

DOI10.1145/3406325.3451053MaRDI QIDQ6087007zbMATH OpenOpenAlexFDO

Authors Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.06112

zbMATH Keywords

approximation algorithmshop-constrained distanceshop-constrained network designtree embeddings

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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.

Recommendations

• Hop-constrained tree-shaped networks
• scientific article; zbMATH DE number 6297807
• Optimal Hop-Constrained Trees for Nonlinear Cost Flow Networks
• On a Network Design Problem That Is Intractable on Trees
• Network design for minimum spanning trees under Hamming distance
• Tree knapsack approaches for local access network design
• scientific article; zbMATH DE number 2080522
• Resilient and low stretch routing through embedding into tree metrics
• Dense edge-disjoint embedding of complete binary trees in interconnection networks
• New formulations and solution procedures for the hop constrained network design problem.

Cited in

(9)

• scientific article; zbMATH DE number 6297807 (Why is no real title available?)
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Adaptive-adversary-robust algorithms via small copy tree embeddings
• Approximation algorithms for directed weighted spanners
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing
• hop-constrained oblivious routing
• Near-optimal directed low-diameter decompositions
• Directed buy-at-bulk spanners

This page was built for publication: Tree embeddings for hop-constrained network design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087007)