DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.66

Bicriteria Approximation for k-Edge-Connectivity

Authors: Zeev Nutov and Reut Cohen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

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.

Cite as

Zeev Nutov and Reut Cohen. Bicriteria Approximation for k-Edge-Connectivity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 66:1-66:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nutov_et_al:LIPIcs.ESA.2025.66,
  author =	{Nutov, Zeev and Cohen, Reut},
  title =	{{Bicriteria Approximation for k-Edge-Connectivity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{66:1--66:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.66},
  URN =		{urn:nbn:de:0030-drops-245343},
  doi =		{10.4230/LIPIcs.ESA.2025.66},
  annote =	{Keywords: k-edge-connected subgraph, bicriteria approximation, iterative LP-rounding}
}

Search Results

Documents authored by Cohen, Reut

Bicriteria Approximation for k-Edge-Connectivity

Abstract

Cite as

Thanks for your feedback!

Could not send message