Seminar by Rajsekar Manokaran
On the Approximability of the Maximum Acyclic Subgraph problem
Rajsekar Manokaran
Royal Institute of Technology, Stockholm, Sweden
Date: Thursday, March 20th, 2014
Time: 3:00 PM
Venue: CS101.Abstract:
Suppose we want to rank a group of chess players based on a collection of matches played between a pair of players. A natural objective is to maximize the fraction of matches in the collection whose outcome was consistent with the ranking --- the winner is the higher ranked player.
This is exactly the Maximum Acyclic Subgraph problem and has been extensively studied in the purview of approximation algorithms. Despite much effort, the best algorithm known satisfies only a half of the matches played. On the other hand, even a random ranking of the players is consistent with half the matches in expectation. In this talk, I will describe why it may be NP-hard to beat the guarantees of the random ranking algorithm.
This talk is based on work with my collaborators: Moses Charikar, Venkatesan Guruswami, Johan Hastad, and Prasad Raghavendra.
About the speaker:
Dr. Manokaran did his BTech (CSE) from IIT Madras and PhD in Computer Science from Princeton University. He is currently a Post-doctoral fellow at KTH Royal Institute of Technology, Sweden.