An improved approximation scheme for the Group Steiner Problem
From MaRDI portal
Publication:2709886
DOI<8::AID-NET2>3.0.CO;2-R 10.1002/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-RzbMath0997.90096OpenAlexW1986201860MaRDI QIDQ2709886
C. S. Helvig, Gabriel Robins, Alexander Z. Zelikovsky
Publication date: 17 April 2001
Full work available at URL: https://doi.org/10.1002/1097-0037(200101)37:1<8::aid-net2>3.0.co;2-r
combinatorial optimizationgraph algorithmsapproximation algorithmsSteiner treesarborescencesgroup Steiner problem
Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
Solving the \(k\)-cardinality assignment problem by transformation, Bounded Degree Group Steiner Tree Problems, $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm, On the minimum corridor connection problem and other generalized geometric problems, Directed Steiner trees with diffusion costs, A practical greedy approximation for the directed Steiner tree problem, Complexity of the minimum-length corridor problem, Online Buy-at-Bulk Network Design, A Practical Greedy Approximation for the Directed Steiner Tree Problem, Improved approximation algorithms for directed Steiner forest, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, Online covering with \(\ell_q\)-norm objectives and applications to network design, Solving group Steiner problems as Steiner problems., Worst-case performance of Wong's Steiner tree heuristic, On rooted \(k\)-connectivity problems in quasi-bipartite digraphs, Generalized network design problems., The polymatroid Steiner problems, A greedy approximation algorithm for the group Steiner problem, On rooted \(k\)-connectivity problems in quasi-bipartite digraphs
Uses Software
Cites Work
