Polynomial integrality gap of flow LP for directed Steiner tree

DOI10.1145/3681791MaRDI QIDQ7023533zbMATH OpenFDO

Authors Shi Li, B. Laekhanukit

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3681791

zbMATH Keywords

directed Steiner treeflow LPintegrality gap

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Linear programming (90C05) Programming involving graphs or networks (90C35)

Cites work

• O(^2 k/ k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• An improved LP-based approximation for Steiner tree
• Approximating the weight of shallow Steiner trees
• Approximation Algorithms for Directed Steiner Problems
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• scientific article; zbMATH DE number 1775395 (Why is no real title available?)
• scientific article; zbMATH DE number 2119644 (Why is no real title available?)
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Polylogarithmic inapproximability
• Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results

This page was built for publication: Polynomial integrality gap of flow LP for directed Steiner tree

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