  This study investigated typical performance of approximation algorithms known
as belief propagation, greedy algorithm, and linear-programming relaxation for
maximum coverage problems on sparse biregular random graphs. After using the
cavity method for a corresponding hard-core lattice--gas model, results show
that two distinct thresholds of replica-symmetry and its breaking exist in the
typical performance threshold of belief propagation. In the low-density region,
the superiority of three algorithms in terms of a typical performance threshold
is obtained by some theoretical analyses. Although the greedy algorithm and
linear-programming relaxation have the same approximation ratio in worst-case
performance, their typical performance thresholds are mutually different,
indicating the importance of typical performance. Results of numerical
simulations validate the theoretical analyses and imply further mutual
relations of approximation algorithms.
