A 7/3-approximation for feedback vertex sets in tournaments

Publikationstyp
Conference Paper
Date Issued
2016
Sprache
English
Author(s)
Mnich, Matthias  orcid-logo
Vassilevska Williams, Virginia  
Végh, Lászlo A.  
TORE-URI
http://hdl.handle.net/11420/4573
First published in
Leibniz international proceedings in informatics (LIPIcs)  
Number in series
57
Article Number
67
Citation
Leibniz international proceedings in informatics (LIPIcs) 57: 67 (2016)
Contribution to Conference
24th Annual European Symposium on Algorithms (ESA 2016)  
Publisher DOI
10.4230/LIPIcs.ESA.2016.67
ArXiv ID
1511.01137
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].
DDC Class
004: Informatik