This page lists the colloquiums conducted by the Department of CSE, IIT Palakkad.

Talks

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.