Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
- 20 May 2024
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 86 (8) , 2575-2604
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Office of Naval Research (N00014-21-1-2575)
- Natural Sciences and Engineering Research Council of Canada (RGPIN-2019-04197, 327620-09, and NSERC DAS award)
- Horizon 2020 (ScaleOpt 757481)
- Dutch Research Council NWO Vidi (016.Vidi.189.087)
This publication has 30 references indexed in Scilit:
- Graph Theory2017
- Approximability of Capacitated Network DesignAlgorithmica, 2014
- Approximating the smallest k‐edge connected spanning subgraph by LP‐roundingNetworks, 2008
- Deformable Polygon Representation and Near-Mincuts2008
- Approximation Algorithms2003
- A Factor 2 Approximation Algorithm for the Generalized Steiner Network ProblemCombinatorica, 2001
- An efficient approximation algorithm for the survivable network design problemMathematical Programming, 1998
- A primal-dual approximation algorithm for generalized steiner network problemsCombinatorica, 1995
- Approximation Algorithms for Graph AugmentationJournal of Algorithms, 1993
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955