  Finding a minimum vertex cover in a network is a fundamental NP-complete
graph problem. One way to deal with its computational hardness, is to trade the
qualitative performance of an algorithm (allowing non-optimal outputs) for an
improved running time. For the vertex cover problem, there is a gap between
theory and practice when it comes to understanding this tradeoff. On the one
hand, it is known that it is NP-hard to approximate a minimum vertex cover
within a factor of $\sqrt{2}$. On the other hand, a simple greedy algorithm
yields close to optimal approximations in practice.
  A promising approach towards understanding this discrepancy is to recognize
the differences between theoretical worst-case instances and real-world
networks. Following this direction, we close the gap between theory and
practice by providing an algorithm that efficiently computes nearly optimal
vertex cover approximations on hyperbolic random graphs; a network model that
closely resembles real-world networks in terms of degree distribution,
clustering, and the small-world property. More precisely, our algorithm
computes a $(1 + o(1))$-approximation, asymptotically almost surely, and has a
running time of $\mathcal{O}(m \log(n))$.
  The proposed algorithm is an adaptation of the successful greedy approach,
enhanced with a procedure that improves on parts of the graph where greedy is
not optimal. This makes it possible to introduce a parameter that can be used
to tune the tradeoff between approximation performance and running time. Our
empirical evaluation on real-world networks shows that this allows for
improving over the near-optimal results of the greedy approach.
