Department Seminar Series
Improved Approximation Algorithm for Minimum Feedback Vertex Sets in Tournaments
19th May 2016, 13:00
H223 (George Holt LT)
Dr. Matthias Mnich
University of Bonn
Institute of
Computer Science, Dept. I
Room E.
Friedrich-Ebert-Allee 144
D-53113 Bonn
Abstract
We consider the minimum feedback vertex set problem in tournaments, which finds applications in ranking scenarios. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than two. We present the first 7/3-approximation algorithm for this problem; this improves on the previously best known ratio 5/2, given by Cai et al. in FOCS 1998 / SICOMP 2001.
(Joint work with Laszlo A. Vegh and Virginia Vassilevska Williams).
Maintained by Othon Michail