A greedy approximation algorithm for the group Steiner problem

DOI10.1016/j.dam.2005.07.010zbMath1083.68089OpenAlexW2014979132MaRDI QIDQ2581556

Guy Even, Guy Kortsarz, Chandra Chekuri

Publication date: 10 January 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.07.010

zbMATH Keywords

polylogarithmic ratio approximation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

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 ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Affinity-driven blog cascade analysis and prediction ⋮ Combination algorithms for Steiner tree variants ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Tour recommendation for groups ⋮ On a class of branching problems in broadcasting and distribution ⋮ Approximating the two-level facility location problem via a quasi-greedy approach ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Combinatorial optimization in system configuration design ⋮ The polymatroid Steiner problems ⋮ On fixed cost \(k\)-flow problems

Cites Work

• A series of approximation algorithms for the acyclic directed Steiner tree problem
• The Steiner problem with edge lengths 1 and 2
• Approximating the weight of shallow Steiner trees
• An improved approximation scheme for the Group Steiner Problem
• On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem
• A threshold of ln n for approximating set cover
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation algorithms for the covering Steiner problem
• Approximation Algorithms for Directed Steiner Problems
• Approximating min-sum k -clustering in metric spaces
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item