This page lists the colloquiums conducted by the Department of CSE, IIT Palakkad.
01 February 2023 | Selecting Vertices at Random
- Speaker: Prof. Saket Saurabh (The Institute of Mathematical Sciences, Chennai)
- Venue: Room no 33, Ahalia Campus
- 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.