On the Approximability of the Maximum Acyclic Subgraph problem 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.
Reference and Copyrights:
Moses Charikar, Venkatesan Guruswami, Johan Hastad, and Prasad Raghavendra.
http://www.cse.iitk.ac.in/research/seminars/2013-14/2014.3.20.html
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.
We prepared and published this seminar abstract for final year engineering students seminar research. You should do your own research additional to this information before presenting your seminar.
Please include "Reference: Collegelib.com" and link back to this page in your work.
Subscribe via email for more Latest topics
12 Steps to boost your innovative project ideas
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.
Reference and Copyrights:
Moses Charikar, Venkatesan Guruswami, Johan Hastad, and Prasad Raghavendra.
http://www.cse.iitk.ac.in/research/seminars/2013-14/2014.3.20.html
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.
We prepared and published this seminar abstract for final year engineering students seminar research. You should do your own research additional to this information before presenting your seminar.
Please include "Reference: Collegelib.com" and link back to this page in your work.
Subscribe via email for more Latest topics
12 Steps to boost your innovative project ideas