Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions

DOI10.4230/LIPICS.ICALP.2023.15MaRDI QIDQ6638007zbMATH OpenFDO

Authors Ishan Bansal, Joseph Cheriyan, Logan Grout, Sharat Ibrahimpur

Publication date 14 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2023.15

zbMATH Keywords

approximation algorithmsedge-connectivity of graphsf-connectivity problemflexible graph connectivityminimum cutsnetwork designprimal-dual methodsmall cuts

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(11)

• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• An O( n)-approximation algorithm for (p, q)-flexible graph connectivity via independent rounding
• On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model
• Improved approximation algorithms for covering pliable set families and flexible graph connectivity
• Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
• Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
• Improved approximations for flexible network design
• When does FTP become FPT??
• When does FTP become FPT?
• Tight analysis of the primal-dual method for edge-covering pliable set families
• Fault-tolerant matroid bases

This page was built for publication: Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions

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