Please note: This seminar will take place in DC 1304 and online.
Chaitanya Swamy, Professor
Department of Combinatorics and Optimization
We consider the k-edge connected spanning subgraph} (kECSS) problem, where we are given an undirected graph with nonnegative edge costs, and we seek a minimum-cost subgraph that is k-edge connected, i.e., there are k edge-disjoint paths between every pair of nodes.
For even k, we present a polytime algorithm that computes a (k-2)-edge connected subgraph of cost at most the optimal value of the natural LP-relaxation for kECSS; for odd k, this leads to a (k-3)-edge connected subgraph of cost at most the LP optimum. Since kECSS is APX-hard for all k\geq 2, the tightest connectivity guarantee one can hope for without exceeding the optimal value is (k-1)-edge connectivity, so our results are nearly tight. They also significantly improve upon the recent work of Hershkowitz et al., both in terms of solution quality and the simplicity of algorithm and its analysis. Our result is obtained using iterative rounding, with additional insights involving uncrossing tight sets for kECSS. A slight variant of our approach yields a (k-1)-edge connected subgraph of cost at most 1.5 times the LP optimum; with unit edge costs, the cost guarantee improves to (1+4/3k) times the LP optimum, which improves upon the state-of-the-art approximation for unit edge costs, but with a unit loss in edge connectivity. The kECSS-result also yields results for the k-edge connected spanning multigraph (kECSM) problem, where multiple copies of an edge can be selected. Our techniques extend to the degree-bounded versions of kECSS and kECSM, wherein we also impose degree lower- and upper- bounds on the nodes.
The talk will be self contained. Joint work with Nikhil Kumar, C&O.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.