Thursday, June 19, 2025 1:00 pm
-
2:30 pm
EDT (GMT -04:00)
Title: Almost Tight Additive Guarantees for k-Edge-Connectivity
| Speaker: | Nikhil Kumar |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: We consider the k-edge-connected spanning subgraph (k-ECSS) problem, where we are given an undirected graph G = (V, E) with nonnegative edge costs, and the goal is to find a minimum-cost subgraph H of G that is k-edge-connected; that is, there exist at least k edge-disjoint paths between every pair of vertices in H.
For even k, we present a polynomial-time algorithm that computes a (k−2)-edge-connected subgraph whose cost is at most that of the natural LP relaxation of k-ECSS. I will try to present an overview of our algorithm and analysis, which is based on the iterative rounding technique.