Fast and Survivable Network Design

15^th October 2024, 13:00 Ashton Lecture Theatre
Parinya Chalermsook
Aalto University

Abstract

Designing the cost-effective network (subgraph) that is guaranteed to be resilient against node or link failures is a fundamental problem in algorithms and optimization. The seminal result of Jain (2001) presents an elegant polynomial-time 2-approximation algorithm for a very general class of survivable network design problems. In this talk, we consider the question of achieving the same guarantee with a fast (near-linear time) algorithm. We show a fast algorithm for the case of k-Edge Connected Spanning Subgraphs (kECSS), a large and natural subclass of survivable network design that has received a lot of attention for more than 3 decades.

Joint with C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, and S. Yingcharoenthawornchai

Biography

Parinya Chalermsook is an Associate Professor at Aalto University, Finland, specializing in the intersection of algorithms and optimization. He has worked on combinatorial problems arising in various domains, including graphs, geometry, data structures, and algorithmic game theory. Parinya has mentored 5 postdoctoral researchers, 6 PhD students, 8 master's students, and 14 other mentees through internships and informal mentoring. He has been recognized with several early-career awards, such as the ERC Starting Grant (2018), Simons-Berkeley Research Fellowship (2017), and Academy of Finland Research Fellowship (2017).

Additional Materials

• https://arxiv.org/abs/2205.14978