Speaker
Description
Ishan Bansal, Joe Cheriyan, Logan Grout and Sharat Ibrahimpur
Abstract: 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 guarantee of two for connectivity augmentation problems where the connectivity requirements can be specified by so-called 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. This property characterizes uncrossable functions \dots\ 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 guarantee via the primal-dual method for a class of functions that generalizes the notion of an uncrossable function. We mention that the support of every optimal dual solution could be non-laminar for instances that can be handled by our methods.
We present a few applications of our main result to problems in the area of network design.
(a) A 16-approximation algorithm for augmenting the family of near-minimum cuts of a graph $G$.
The previous best approximation guarantee was $O(\log |V(G)|)$.
(b) A 20-approximation algorithm for the model of $(p,2)$-Flexible Graph Connectivity.
The previous best approximation guarantee was $O(\log |V(G)|)$, where $G$ denotes the input graph.
(c) A $16 \cdot {\lceil k/u_{min} \rceil}$-approximation algorithm for the Cap-$k$-ECSS problem which is as follows:
Given an undirected graph $G = (V,E)$ with edge costs $c$ and edge capacities $u$, find a minimum cost subset of the edges $F\subseteq 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} \leq k$.
The previous best approximation guarantee was $\min( O(\log{n}), k, 2u_{max} )$.