A primal-dual algorithm for the generalized prize-collecting Steiner forest problem

DOI10.1007/S40305-017-0164-4zbMath1390.90465OpenAlexW2611727281MaRDI QIDQ1706681

Lu Han, Da-Chuan Xu, Chen-Chen Wu, Dong-lei Du

Publication date: 28 March 2018

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-017-0164-4

zbMATH Keywords

approximation algorithmprimal-dualSteiner forestprize-collecting

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (2)

An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties

Cites Work

• Unnamed Item
• A note on the prize collecting traveling salesman problem
• New approximation algorithms for the Steiner tree problems
• An 11/6-approximation algorithm for the network Steiner problem
• Approximating the Single-Sink Link-Installation Problem in Network Design
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
• A General Approximation Technique for Constrained Forest Problems
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Steiner Minimal Trees

This page was built for publication: A primal-dual algorithm for the generalized prize-collecting Steiner forest problem