Department of
Applied
Mathematics

Improved Approximation Algorithm for Minimum Feedback Vertex Sets in Tournaments

Matthias Mnich

Abstract

(joint work with László Végh and Virginia Vassilevska Williams)

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.