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

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