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

DOI10.1007/s40314-022-01984-2OpenAlexW4289884389WikidataQ114219257 ScholiaQ114219257MaRDI QIDQ2167423

Yanyan Li

Publication date: 25 August 2022

Published in: Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40314-022-01984-2

zbMATH Keywords

approximation algorithmsubmodular functiongroup prize-collecting Steiner tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Design and analysis of approximation algorithms
• A note on the prize collecting traveling salesman problem
• Approximation algorithms for group prize-collecting and location-routing problems
• Generalized Steiner problems and other variants
• A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
• An efficient transformation of the generalized vehicle routing problem
• Submodular functions and optimization.
• Prize-Collecting Steiner Network Problems
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• On the generalized minimum spanning tree problem
• An Experimental Study of the Treewidth of Real-World Graph Data
• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions
• Integrality Ratio for Group Steiner Trees and Directed Steiner Trees

This page was built for publication: An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties