论文标题
最小总和顶点盖的近似性结果
Some Results on Approximability of Minimum Sum Vertex Cover
论文作者
论文摘要
我们研究最小总和顶点覆盖问题，该问题要求在图中订购顶点，以最大程度地减少边缘的总覆盖时间。特别是，根据订购访问了图的n个顶点，对于每个边缘，这首先覆盖了。问题的目的是找到订购，该顺序最大程度地减少图表中所有边缘的盖子总和。在这项工作中，我们给出了最小总和顶点盖的第一个明确的近似结果。特别是，假设唯一的游戏猜想，我们表明最小总和顶点覆盖问题不能在1.0748之内近似。截至目前，最低总和顶点覆盖率的最佳近似值为16/9，这是由于Bansal，Batra，Farhadi和Tetali的最新工作。我们还研究了常规图上的最小总和顶点覆盖问题。特别是，我们表明在这种情况下，问题很难在1.0157之内近似。我们还重新访问了Feige，Lovász和Tetali工作中概述的常规图的近似算法，以表明在常规图上的1.225中可以在1.225中近似最小总和顶点盖。
We study the Minimum Sum Vertex Cover problem, which asks for an ordering of vertices in a graph that minimizes the total cover time of edges. In particular, n vertices of the graph are visited according to an ordering, and for each edge this induces the first time it is covered. The goal of the problem is to find the ordering which minimizes the sum of the cover times over all edges in the graph. In this work we give the first explicit hardness of approximation result for Minimum Sum Vertex Cover. In particular, assuming the Unique Games Conjecture, we show that the Minimum Sum Vertex Cover problem cannot be approximated within 1.0748. The best approximation ratio for Minimum Sum Vertex Cover as of now is 16/9, due to a recent work of Bansal, Batra, Farhadi, and Tetali. We also study Minimum Sum Vertex Cover problem on regular graphs. In particular, we show that in this case the problem is hard to approximate within 1.0157. We also revisit an approximation algorithm for regular graphs outlined in the work of Feige, Lovász, and Tetali, to show that Minimum Sum Vertex Cover can be approximated within 1.225 on regular graphs.
