Extending the primal-dual 2-approximation algorithm beyond uncrossable set families

DOI10.1007/978-3-031-59835-7_26MaRDI QIDQ7030548zbMATH OpenFDO

Authors Zeev Nutov

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59835-7_26

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Cites work

• A 3/2-approximation algorithm for some minimum-cost graph problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A General Approximation Technique for Constrained Forest Problems
• A primal-dual approximation algorithm for generalized Steiner network problems
• Approximating minimum-cost graph problems with spanning tree edges
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• On fixed cost k-flow problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(1)

• Tight analysis of the primal-dual method for edge-covering pliable set families

This page was built for publication: Extending the primal-dual 2-approximation algorithm beyond uncrossable set families

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