Elementary approximation algorithms for prize collecting Steiner tree problems

DOI10.1016/J.IPL.2007.12.010MaRDI QIDQ963393zbMATH OpenOpenAlexFDO

Authors Shai Gutner

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.12.010

zbMATH Keywords

approximation algorithmsprimal-duallocal ratioprize collecting Steiner tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) 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
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• 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

(20)

• A General Approximation Technique for Constrained Forest Problems
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Prize-collecting Steiner network problems
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• Variations of the prize‐collecting Steiner tree problem
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• Approximation algorithms for group prize-collecting and location-routing problems
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• Euclidean prize-collecting Steiner forest
• 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 Q963393)