Prize-collecting forest with submodular penalties: improved approximation

DOI10.1007/978-3-031-93112-3_2MaRDI QIDQ6880155zbMATH OpenFDO

Authors Ali Ahmadi, Iman Gholami, Mohammad T. Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi

Publication date 22 December 2025

Full work available at URL https://doi.org/10.1007/978-3-031-93112-3_2

zbMATH Keywords

approximation algorithmprize-collectingSteinersubmodularity

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites work

• 2-approximation for prize-collecting Steiner forest
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A General Approximation Technique for Constrained Forest Problems
• A note on the prize collecting traveling salesman problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• An 11/6-approximation algorithm for the network Steiner problem
• An improved LP-based approximation for Steiner tree
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements
• scientific article; zbMATH DE number 6783450 (Why is no real title available?)
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Network design for information networks
• New approximation algorithms for the Steiner tree problems
• Prize-collecting Steiner network problems
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Tighter Bounds for Graph Steiner Tree Approximation
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

This page was built for publication: Prize-collecting forest with submodular penalties: improved approximation

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