  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.
