A 7/3-Approximation for Feedback Vertex Sets in Tournaments
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
复制标题
DOI：
10.4230/lipics.esa.2016.67
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Matthias Mnich;V. V. Williams-V.;László A. Végh
中科院分区：
文献类型：
--
作者：
Matthias Mnich;V. V. Williams-V.;László A. Végh
我们考虑锦标赛中的最小权重反馈顶点集问题：给定具有非负顶点权重的比赛，删除与所有周期相交的最小重量的顶点。这个问题是$ \ mathsf {np} $ - 难以准确解决，独特的游戏近似于一个比2更好的因素。我们提出了第一个$ 7/3 $近似算法的此问题比率$ 5/2 $由Cai等人提供。 [FOCS 1998，SICOMP 2001]。
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 $\mathsf{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].