Seminars

View all Seminars  |  Download ICal for this event

Approximation Algorithms for Network Design in Non-Uniform Fault Models

Series: Bangalore Theory Seminars

Speaker: Chandra Chekuri , University of Illinois, Urbana-Champaign

Date/Time: Nov 03 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
Classical network design models, such as the Survivable Network Design problem (SNDP), are (partly) motivated by robustness to faults under the assumption that any subset of edges up to a specific number can fail. SNDP admits a 2-approximation via the iterated rounding technique of Jain. We consider non-uniform fault models where the subset of edges that fail can be specified in different ways. We consider two models. The first is the flexible graph connectivity model that was introduced by Adjiashvili in 2013, and has seen renewed interest in recent work. The second is the bulk robust model that was considered in a work of Adjiashivili, Sitters and Zenklusen in 2015. The approximability of network design problems in the non-uniform models is much less understood. The talk will explain the models, the connection between them, and some recent progress on approximation algorithms.

Based on joint work with Rhea Jain which appeared in ICALP 2023. Link to paper: Link

Microsoft Teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, Rahul Madhavan, Rachana Gusain, KVN Sreenivas