A 7/3-approximation for feedback vertex sets in tournaments
Mnich, Matthias; Williams, Virginia Vassilevska; and Végh, László A.
(2016)
A 7/3-approximation for feedback vertex sets in tournaments.
Leibniz International Proceedings in Informatics (57).
67:1-67:14.
ISSN 1868-8969
(2016)
A 7/3-approximation for feedback vertex sets in tournaments.
Leibniz International Proceedings in Informatics (57).
67:1-67:14.
ISSN 1868-8969
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first 7/3 approximation algorithm for this problem, improving on the previously best known ratio 5/2 given by Cai et al. [FOCS 1998, SICOMP 2001].
-
picture_as_pdf -
subject - Published Version
-
- Available under Creative Commons: Attribution 4.0
Downloads