Seminars

View all Seminars  |  Download ICal for this event

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding

Series: Bangalore Theory Seminars

Speaker: Sharat Ibrahimpur, University of Bonn

Date/Time: Mar 13 14:30:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

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 which 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 Kargers bound on the number of near-minimum cuts.

Based on joint work with László A. Végh: Link


Teams link

Link

We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar