TUHH Open Research
 

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

Publikationstyp
Conference Paper
Date Issued
2016
Sprache
English
Author(s)
Mnich, Matthias  
Vassilevska Williams, Virginia  
Végh, Lászlo A.  
TORE-URI
http://hdl.handle.net/11420/4573
First published in
Leibniz international proceedings in informatics  
Number in series
57
Article Number
67
Citation
24th Annual European Symposium on Algorithms, ESA 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