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

DOI10.1145/1109557.1109626zbMath1192.90228MaRDI 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

90C35: Programming involving graphs or networks

05C05: Trees

Related Items

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