Saket Saurabh: Picking Random At Vertices
- Speaker
- Saket Saurabh
- Affiliation
- 欧洲科学院院士，印度科学院院士，度数学科学学院和挪威卑尔根大学教授
- Date
- Time
- – Asia/Shanghai
- Venue
- 四号科研楼A区518
Abstract
We survey some recent graph algorithms that are based on picking a vertex at random and declaring it to be a part of the solution. This simple idea has been deployed to obtain state-of-the-art parameterized, exact exponential time, and approximation algorithms for a number of problems, such as Feedback Vertex Set and 3-Hitting Set. We will also discuss a recent 2-approximation algorithm for Feedback Vertex Set in Tournaments that
is based on picking a vertex at random and declaring it to not be part of the solution.
Speaker Bio
Saket Saurabh received his PhD in Computer Science (2008), from The Institute of Mathematical 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 and at Department of Informatics at the University of Bergen. His main research interests are in graph algorithms, parameterized algorithms and complexity. He has written more than 300 articles, graduated more than 15 PhD students, and mentored around 10 post doctoral fellows. He is a co-author of two books: Parameterized Algorithms and Kernelization theory of parameterized preprocessing.
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). He is also the recipient of an ERC starting grant and an ERC Consolidator Grants in parameterized algorithms. He was also named one of the ACM Distinguished Members in 2022.
Poster
