Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
From MaRDI portal
Publication:1881568
DOI10.1007/s10107-003-0479-2zbMath1116.90104OpenAlexW2767048380MaRDI QIDQ1881568
David P. Williamson, Tim Roughgarden, Fabián A. Chudak
Publication date: 5 October 2004
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-003-0479-2
Related Items (18)
Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Primal-dual approximation algorithms for the prize-collecting Steiner tree problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Pruning 2-connected graphs ⋮ A unified approach to approximating partial covering problems ⋮ Approximation algorithm for minimizing total latency in machine scheduling with deliveries ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Virtual machine placement for minimizing connection cost in data center networks ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem ⋮ Approximating minimum-cost connected \(T\)-joins
This page was built for publication: Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
