Speaker:

Qingyun Chen (University of California, Merced)

Time:

• 10:00-11:00 (Time in Beijing)
• May 14, 2024 (Tuesday)

Venue:

B1-104，Main building

Abstract:

In the classical survivable network design problem (SNDP), we are given an undirected graph G=(V,E) with costs on edges and a connectivity requirement k(s,t) for each pair of vertices. The goal is to find a minimum-cost subgraph H\subseteq G such that every pair (s,t) are connected by k(s,t) edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS’98, Combinatorica’01] gives a 2-approximation algorithm for EC-SNDP, and a decade later, an O(k^3\log n) -approximation algorithm for VC-SNDP, where k is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS’09, Theory Comput.’12]. While there is a rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood.

This paper concerns the generalization of SNDP into the subset-to-subset setting, namely Group EC-SNDP. We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group EC-SNDP. Previously, only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA’15], and a true approximation algorithm is known only for the single-source variant with connectivity requirement k(S,T)\in{0,1,2} [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor. Comput. Sci.’12].

Bio:

Qingyun Chen is a PhD student in EECS at UC Merced, advised by Professor Sungjin Im. His research focuses on theoretical computer science, in particular, approximation algorithms, online algorithms, and hardness of approximations.