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

DOI10.1007/s00453-024-01235-2MaRDI QIDQ6586662zbMATH OpenFDO

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

Publication date 13 August 2024

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsnetwork designprimal-dual methodminimum cutsedge-connectivity of graphsf-connectivity problemflexible graph connectivitysmall cuts

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites work

• scientific article; zbMATH DE number 1003253 (Why is no real title available?)
• scientific article; zbMATH DE number 871924 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A Fast Algorithm for Optimally Increasing the Edge Connectivity
• A General Approximation Technique for Constrained Forest Problems
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A new approach to the minimum cut problem
• A primal-dual approximation algorithm for generalized Steiner network problems
• An efficient approximation algorithm for the survivable network design problem
• Approximability of capacitated network design
• Approximating the smallest \(k\)-edge connected spanning subgraph by LP-rounding
• Approximation Algorithms for Graph Augmentation
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for network design in non-uniform fault models
• Biconnectivity approximations and graph carvings
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
• Computing All Small Cuts in an Undirected Network
• Connections in combinatorial optimization
• Deformable Polygon Representation and Near-Mincuts
• Flexible graph connectivity
• Graph theory
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• Iterated rounding algorithms for the smallest k-edge connected spanning subgraph
• Iterative methods in combinatorial optimization.
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
• The design of approximation algorithms
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(1)

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

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 Q6586662)