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 algorithmslocal ratioprimal-dualprize collecting Steiner tree problem

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• 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

(24)

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

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)