Abstract
We address longstanding open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primaldual method (Combinatorica 15(3):435454, 1995). Williamson et al. prove an approximation ratio of two for connectivity augmentation problems where the connectivity requirements can be specified by uncrossable functions. They state: "Extending our algorithm to handle nonuncrossable functions remains a challenging open problem. The key feature of uncrossable functions is that there exists an optimal dual solution which is laminar... A larger open issue is to explore further the power of the primaldual approach for obtaining approximation algorithms for other combinatorial optimization problems."
Our main result proves a 16approximation ratio via the primaldual method for a class of functions that generalizes the notion of an uncrossable function. There exist instances that can be handled by our methods where none of the optimal dual solutions have a laminar support.
We present applications of our main result to three networkdesign problems.
1) A 16approximation algorithm for augmenting the family of small cuts of a graph G. The previous best approximation ratio was O(log V(G)).
2) A 16⋅⌈k/u_min⌉approximation algorithm for the CapkECSS problem which is as follows: Given an undirected graph G = (V,E) with edge costs c ∈ ℚ_{≥0}^E and edge capacities u ∈ ℤ_{≥0}^E, find a minimum cost subset of the edges F ⊆ E such that the capacity across any cut in (V,F) is at least k; u_min (respectively, u_max) denote the minimum (respectively, maximum) capacity of an edge in E, and w.l.o.g. u_max ≤ k. The previous best approximation ratio was min(O(logV), k, 2u_max).
3) A 20approximation algorithm for the model of (p,2)Flexible Graph Connectivity. The previous best approximation ratio was O(logV(G)), where G denotes the input graph.
BibTeX  Entry
@InProceedings{bansal_et_al:LIPIcs.ICALP.2023.15,
author = {Bansal, Ishan and Cheriyan, Joseph and Grout, Logan and Ibrahimpur, Sharat},
title = {{Improved Approximation Algorithms by Generalizing the PrimalDual Method Beyond Uncrossable Functions}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {15:115:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772785},
ISSN = {18688969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18067},
URN = {urn:nbn:de:0030drops180678},
doi = {10.4230/LIPIcs.ICALP.2023.15},
annote = {Keywords: Approximation algorithms, Edgeconnectivity of graphs, fConnectivity problem, Flexible Graph Connectivity, Minimum cuts, Network design, Primaldual method, Small cuts}
}
Keywords: 

Approximation algorithms, Edgeconnectivity of graphs, fConnectivity problem, Flexible Graph Connectivity, Minimum cuts, Network design, Primaldual method, Small cuts 
Collection: 

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 
Issue Date: 

2023 
Date of publication: 

05.07.2023 