  In this paper we construct an approximation algorithm for the Minimum Vertex
Cover Problem (Min-VC) with an expected approximation ratio of 2-f(beta) for
random Power Law Graphs (PLG) in the (alpha,beta)-model of Aiello et. al.,
where f(beta) is a strictly positive function of the parameter beta. We obtain
this result by combining the Nemhauser and Trotter approach for Min-VC with a
new deterministic rounding procedure which achieves an approximation ratio of
3/2 on a subset of low degree vertices for which the expected contribution to
the cost of the associated linear program is sufficiently large.
