Integrality Ratio for Group Steiner Trees and Directed Steiner Trees
From MaRDI portal
Publication:5422497
DOI10.1137/S0097539704445718zbMath1124.05027MaRDI QIDQ5422497
Robert Krauthgamer, Eran Halperin, Nan Wang, Aravind Srinivasan, Guy Kortsarz
Publication date: 22 October 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
linear programming relaxationapproximation algorithmsdirected Steiner treeintegrality ratioflow-based relaxationGroup Steiner tree
Trees (05C05) Integer programming (90C10) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
On Directed Steiner Trees with Multiple Roots, An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties, Static and dynamic routing under disjoint dominant extreme demands, An Efficient Approximation Algorithm for the Steiner Tree Problem, Approximating \(k\)-generalized connectivity via collapsing HSTs, An improved algorithm for the Steiner tree problem with bounded edge-length, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, Balls and Funnels: Energy Efficient Group-to-Group Anycasts
