Tata Institute of Fundamental Research
Invitation to FPT Approximation via Cut and Coverage Problems
STCS Seminar
Speaker:
Saket Saurabh (The Institute of Mathematical Sciences)
Organiser:
Raghuvansh Saxena
Date:
Tuesday, 6 Aug 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In this talk, we will provide an introduction to the area of FPT-Approximation. The goal of this research area is to develop algorithms that are faster than known FPT algorithms and achieve better approximation factors than what is possible in polynomial time. We will explore recent advances in this field through some classical cut and coverage problems, such as k-Way Cut and Max-Coverage.
Short Bio:
Saket Saurabh received his PhD in Computer Science (2008), from The Institute of Mathe-matical Sciences (IMSc), Chennai. Saurabh spent two years (2007-2009) as a Postdoctoral Fellow at University of Bergen, Norway, and is now a professor at IMSc. He is a SwarnaJayanti Fellow in Mathematical Sciences (2018), Fellow of Indian Academy of Sciences (2020), Academia Europaea (2020), and European Association for Theoretical Computer Science (EATCS, 2021). He received the inaugural ACM India Early Career Researcher Award in 2020, and Shanti Swarup Bhatnagar Prize (SSB) for Science and Technology 2021 (Mathematical Science).
| Speaker: | Saket Saurabh (The Institute of Mathematical Sciences) |
| Organiser: | Raghuvansh Saxena |
| Date: | Tuesday, 6 Aug 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
In this talk, we will provide an introduction to the area of FPT-Approximation. The goal of this research area is to develop algorithms that are faster than known FPT algorithms and achieve better approximation factors than what is possible in polynomial time. We will explore recent advances in this field through some classical cut and coverage problems, such as k-Way Cut and Max-Coverage.
Short Bio:
Saket Saurabh received his PhD in Computer Science (2008), from The Institute of Mathe-matical Sciences (IMSc), Chennai. Saurabh spent two years (2007-2009) as a Postdoctoral Fellow at University of Bergen, Norway, and is now a professor at IMSc. He is a SwarnaJayanti Fellow in Mathematical Sciences (2018), Fellow of Indian Academy of Sciences (2020), Academia Europaea (2020), and European Association for Theoretical Computer Science (EATCS, 2021). He received the inaugural ACM India Early Career Researcher Award in 2020, and Shanti Swarup Bhatnagar Prize (SSB) for Science and Technology 2021 (Mathematical Science).