2026-10-13T12:10:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24534 2025-12-16T13:00:28Z ddc:004 open_access

Bicriteria Approximation for k-Edge-Connectivity Nutov, Zeev Cohen, Reut k-edge-connected subgraph bicriteria approximation iterative LP-rounding In the k-Edge Connected Spanning Subgraph (k-ECSS) problem we are given a (multi-)graph G = (V,E) with edge costs and an integer k, and seek a min-cost k-edge-connected spanning subgraph of G. The problem admits a 2-approximation algorithm and no better approximation ratio is known. Recently, Hershkowitz, Klein, and Zenklusen [STOC 24] gave a bicriteria (1,k-10)-approximation algorithm that computes a (k-10)-edge-connected spanning subgraph of cost at most the optimal value of a standard Cut-LP for k-ECSS. We improve the bicriteria approximation to (1,k-4) and also give another non-trivial bicriteria approximation (3/2,k-2). The k-Edge-Connected Spanning Multi-subgraph (k-ECSM) problem is almost the same as k-ECSS, except that any edge can be selected multiple times at the same cost. A (1,k-p) bicriteria approximation for k-ECSS w.r.t. Cut-LP implies approximation ratio 1+p/k for k-ECSM, hence our result also improves the approximation ratio for k-ECSM. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeev Nutov and Reut Cohen 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.66 urn:nbn:de:0030-drops-245343 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.66 eng https://creativecommons.org/licenses/by/4.0/legalcode