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\'asz, and Tetali, to show that Minimum Sum Vertex Cover can be approximated within 1.225 on regular graphs.
翻译:我们研究了最小值折合点覆盖问题, 这个问题要求用一个能最大限度地减少覆盖边缘时间的总时间的图表来排序顶部。 特别是, 图形的n 顶部根据一个订单来查看, 并且对每个边缘来说, 这个问题第一次被覆盖。 问题的目标是找到一个能够将覆盖时间总和最小值在图形所有边缘上最小值的排序。 在这项工作中, 我们给出最小值折合点覆盖面的初近结果的第一个明确硬度 。 特别是, 假设奇特奥奥会洞穴, 我们显示最小值折合点覆盖问题无法在 1. 07. 48 范围内接近。 由于Bansal、 Batra、 Farhadi 和 Tetali 最近的一项工作, 目前最低值折合层盖面的最接近率为 16/ 9 。 我们还在普通图上研究最小值折合点覆盖点覆盖时间的问题 。 特别是, 在此情况下, 问题很难在 1. 0157 范围内。 我们还重新查看Feggegge、 Lov\\\ 1.2 最低值 和 Teatex 的常规图上显示最低值 1.2 。