2026-07-26T04:13:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18067 2024-03-06T11:00:55Z ddc:004 open_access

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions Bansal, Ishan Cheriyan, Joseph Grout, Logan Ibrahimpur, Sharat Approximation algorithms Edge-connectivity of graphs f-Connectivity problem Flexible Graph Connectivity Minimum cuts Network design Primal-dual method Small cuts We address long-standing open questions raised by Williamson, Goemans, Vazirani and Mihail pertaining to the design of approximation algorithms for problems in network design via the primal-dual method (Combinatorica 15(3):435-454, 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 non-uncrossable 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 primal-dual approach for obtaining approximation algorithms for other combinatorial optimization problems." Our main result proves a 16-approximation ratio via the primal-dual 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 network-design problems. 1) A 16-approximation 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 Cap-k-ECSS 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(log|V|), k, 2u_max). 3) A 20-approximation algorithm for the model of (p,2)-Flexible Graph Connectivity. The previous best approximation ratio was O(log|V(G)|), where G denotes the input graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishan Bansal and Joseph Cheriyan and Logan Grout and Sharat Ibrahimpur 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.15 urn:nbn:de:0030-drops-180678 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.15 eng https://creativecommons.org/licenses/by/4.0/legalcode