| Title | : | An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding |
| Speaker | : | Sharat Ibrahimpur (University of Bonn, Germany) |
| Details | : | Fri, 14 Mar, 2025 10:00 AM @ SSB 334 |
| Abstract: | : | In this talk, I will present improved approximation algorithms for the Flexible Graph Connectivity (FGC) model of Adjiashvili, Hommelsheim and Mühlenthaler (IPCO 2020). Since its introduction, the FGC model has received a lot of interest as it offers new means of capturing non-uniformity of edges that appear in survivable network design applications. In this setting, we are given a graph G = (V,E) whose edges have nonnegative costs and they are either safe and unsafe. The algorithmic goal in the (p,q)-FGC problem is to find a minimum cost set of edges F such that the subgraph (V,F) remains p-edge-connected after removing any q unsafe edges from F, for some given connectivity and robustness parameters p and q, respectively.
I will present a new integer programming formulation for the (p,q)-FGC problem that is obtained by adding knapsack cover constraints to the capacitated p(p+q)-edge-connectivity formulation studied in previous work. I will then show that the associated linear relaxation can be solved in polynomial time by giving an efficient separation oracle. Complementing this, we will see that a simple independent randomized rounding of the LP solution yields an O(log n)-approximation for general values of p and q, improving the state-of-the-art O(q log n). For both separation and rounding, a key insight is to use Karger's bound on the number of near-minimum cuts.
Based on joint work with László A. Végh: https://arxiv.org/abs/2501.12549.
Brief Bio: Sharat Ibrahimpur is a postdoctoral researcher at the Research Institute for Discrete Mathematics in Bonn, Germany. Before this, he held a postdoctoral position at the London School of Economics and Political Science in the UK. Sharat obtained his Masters and PhD degrees in Combinatorics and Optimization from the University of Waterloo in Canada where he was advised by Dr. Chaitanya Swamy. Sharat's research work is primarily in designing approximation algorithms for combinatorial optimization problems with recent focus on stochastic optimization and network design. Going further back, he obtained his undergraduate degree in Applied Mathematics from IIT Roorkee. Looking forward to seeing all of you there! |
