A global analysis of the primal-dual method for edge augmentation problems

DOI10.1007/978-3-031-93112-3_5MaRDI QIDQ6880149zbMATH OpenFDO

Authors Ishan Bansal

Publication date 22 December 2025

Full work available at URL https://doi.org/10.1007/978-3-031-93112-3_5

zbMATH Keywords

approximation algorithmsedge augmentationnetwork designprimal-dual method

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Cites work

• 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
• A primal–dual schema based approximation algorithm for the element connectivity problem
• Algorithms for 2-connected network design and flexible Steiner trees with a constant number of terminals
• Approximability of capacitated network design
• Approximation algorithms for flexible graph connectivity
• Approximation algorithms for network design in non-uniform fault models
• Flexible graph connectivity
• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions

Cited in

(3)

• An O( n)-approximation algorithm for (p, q)-flexible graph connectivity via independent rounding
• Protecting the connectivity of a graph under nonuniform edge failures
• Tight guarantees for cut-relative survivable network design via a decomposition technique

This page was built for publication: A global analysis of the primal-dual method for edge augmentation problems

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