Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems

DOI10.1007/978-3-540-85097-7_23MaRDI QIDQ5505663zbMATH OpenOpenAlexFDO

Authors Shai Gutner

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_23

zbMATH Keywords

approximation algorithmsprimal-duallocal ratioprize collecting Steiner tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Recommendations

• Elementary approximation algorithms for prize collecting Steiner tree problems
• A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• scientific article; zbMATH DE number 1445375

Cites work

• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A group-strategyproof mechanism for Steiner forests
• A note on the prize collecting traveling salesman problem
• A unified approach to approximating resource allocation and scheduling
• An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Network design for information networks
• On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
• One for the price of two: a unified approach for approximating covering problems
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(23)

• Approximation algorithms for Steiner forest: An experimental study
• A General Approximation Technique for Constrained Forest Problems
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Elementary approximation algorithms for prize collecting Steiner tree problems
• Prize-collecting Steiner network problems
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• A better approximation algorithm for the budget prize collecting tree problem.
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• Near-optimal online algorithms for prize-collecting Steiner problems
• An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
• Approximation algorithm with constant ratio for stochastic prize-collecting Steiner tree problem
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Approximation algorithms for group prize-collecting and location-routing problems
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• Combinatorial optimization in system configuration design
• An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• A primal-dual approximation algorithm for the Steiner forest problem
• A local-search algorithm for Steiner forest
• On the integrality gap of the prize-collecting Steiner forest LP
• A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
• A 4-approximation algorithm for k-prize collecting Steiner tree problems
• A 2-approximation for the \(k\)-prize-collecting Steiner tree problem

This page was built for publication: Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems

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