Directed spanners via flow-based linear programs

DOI10.1145/1993636.1993680MaRDI QIDQ5419102zbMATH OpenOpenAlexFDO

Authors Michael Dinitz, Robert Krauthgamer

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.3701, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.228.3087

zbMATH Keywords

linear programmingapproximation algorithmsspanners

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: We examine directed spanners through flow-based linear programming relaxations. We design an $O(n^{2/3})$-approximation algorithm for the directed $k$-spanner problem that works for all $kgeq1$, which is the first sublinear approximation for arbitrary edge-lengths. Even in the more restricted setting of unit edge-lengths, our algorithm improves over the previous $O(n^{1-1/k})$ approximation of Bhattacharyya et al. when $kge4$. For the special case of $k=3$ we design a different algorithm achieving an $O(sqrtn)$-approximation, improving the previous $O(n^{2/3})$. Both of our algorithms easily extend to the fault-tolerant setting, which has recently attracted attention but not from an approximation viewpoint. We also prove a nearly matching integrality gap of $Omega(n^{frac13-epsilon})$ for any constant $epsilon>0$. A virtue of all our algorithms is that they are relatively simple. Technically, we introduce a new yet natural flow-based relaxation, and show how to approximately solve it even when its size is not polynomial. The main challenge is to design a rounding scheme that "coordinates" the choices of flow-paths between the many demand pairs while using few edges overall. We achieve this, roughly speaking, by randomization at the level of vertices.

Recommendations

• Improved approximation for the directed spanner problem
• Approximation algorithms for spanner problems and directed Steiner forest
• Approximating low-stretch spanners
• Fault-tolerant spanners
• Finding sparser directed spanners

Cited in

(21)

• Graph spanners: a tutorial review
• Lasserre integrality gaps for graph spanners and related problems
• Approximating approximate distance oracles
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
• Approximation algorithms for directed weighted spanners
• Distributed spanner approximation
• Approximating low-stretch spanners
• Network flow spanners
• Online Directed Spanners and Steiner Forests.
• Network Flow Spanners
• Fault tolerant max-cut
• Roundtrip spanners with (2k-1) stretch
• scientific article; zbMATH DE number 7561533 (Why is no real title available?)
• Simple approximations for general spanner problems
• Sparsification lower bound for linear spanners in directed graphs
• scientific article; zbMATH DE number 7650078 (Why is no real title available?)
• Approximation algorithms for spanner problems and directed Steiner forest
• Improved approximation for the directed spanner problem
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Distributed distance-bounded network design through distributed convex programming

This page was built for publication: Directed spanners via flow-based linear programs

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