Speaker: Dr. Pranabendu Misra (Max Planck Institute for Informatics,
Saarbrucken, Germany)
Date-time: Monday (June 22), 4-5 PM (Webex Meeting details below)
Title: A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments
Abstract
-----------
A Tournament is a directed graph T such that every pair of vertices is
connected by an arc. A Feedback Vertex Set is a set S of vertices in T
such that T−S is acyclic. We consider the Feedback Vertex Set problem
in tournaments, where the input is a tournament T and a weight
function w:V(T)→N and the task is to find a feedback vertex set S in T
minimizing w(S). We give the first polynomial time factor 2
approximation algorithm for this problem. Assuming the Unique Games
conjecture, this is the best possible approximation ratio achievable
in polynomial time.
Meeting link:
https://iitbombay.webex.com/iitbombay/j.php?MTID=md23f92c26686aa030456a9d08390379d
Meeting number:166 483 6041
Password:RKypRMZy888