The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema

DOI10.1145/1109557.1109626zbMath1192.90228OpenAlexW4249586771MaRDI QIDQ3581584

No author found.

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109626

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05)

Related Items (31)

An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ An approximation algorithm for the group prize-collecting Steiner tree problem with submodular penalties ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property ⋮ Additive stabilizers for unstable graphs ⋮ Approximation algorithms for prize-collecting capacitated network design problems ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Pruning 2-connected graphs ⋮ Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ Euclidean prize-collecting Steiner forest ⋮ A unified approach to approximating partial covering problems ⋮ A 2-approximation algorithm and beyond for the minimum diameter \(k\)-Steiner forest problem ⋮ Unnamed Item ⋮ A primal-dual algorithm for the generalized prize-collecting Steiner forest problem ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Online constrained forest and prize-collecting network design ⋮ Local search algorithms for the red-blue median problem ⋮ Elementary approximation algorithms for prize collecting Steiner tree problems ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Approximation Algorithms for Prize-Collecting Network Design Problems with General Connectivity Requirements ⋮ Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ Approximating \(k\)-forest with resource augmentation: a primal-dual approach ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ A note on the subadditive network design problem ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems

This page was built for publication: The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema