Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
From MaRDI portal
Publication:6586662
DOI10.1007/s00453-024-01235-2MaRDI QIDQ6586662
Sharat Ibrahimpur, Joseph Cheriyan, Logan Grout, Ishan Bansal
Publication date: 13 August 2024
Published in: Algorithmica (Search for Journal in Brave)
primal-dual methodnetwork designapproximation algorithmsminimum cutsedge-connectivity of graphsf-connectivity problemflexible graph connectivitysmall cuts
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A factor 2 approximation algorithm for the generalized Steiner network problem
- An efficient approximation algorithm for the survivable network design problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A primal-dual approximation algorithm for generalized Steiner network problems
- Flexible graph connectivity
- Approximability of capacitated network design
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Graph Theory
- Iterated Rounding Algorithms for the Smallest k-Edge Connected Spanning Subgraph
- The Design of Approximation Algorithms
- Approximating the smallest k -edge connected spanning subgraph by LP-rounding
- Iterative Methods in Combinatorial Optimization
- Deformable Polygon Representation and Near-Mincuts
- Approximation Algorithms for Several Graph Augmentation Problems
- Approximation Algorithms for Graph Augmentation
- Biconnectivity approximations and graph carvings
- A new approach to the minimum cut problem
- A Fast Algorithm for Optimally Increasing the Edge Connectivity
- Computing All Small Cuts in an Undirected Network
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
- Approximation algorithms for flexible graph connectivity
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- Approximation algorithms for network design in non-uniform fault models
This page was built for publication: Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
