  Typical performance of approximation algorithms is studied for randomized
minimum vertex cover problems. A wide class of random graph ensembles
characterized by an arbitrary degree distribution is discussed with some
theoretical frameworks. Here three approximation algorithms are examined; the
linear-programming relaxation, the loopy-belief propagation, and the
leaf-removal algorithm. The former two algorithms are analyzed using the
statistical-mechanical technique while the average-case analysis of the last
one is studied by the generating function method. These algorithms have a
threshold in the typical performance with increasing the average degree of the
random graph, below which they find true optimal solutions with high
probability. Our study reveals that there exist only three cases determined by
the order of the typical-performance thresholds. We provide some conditions for
classifying the graph ensembles and demonstrate explicitly examples for the
difference in the threshold.
