Typical approximation performance for maximum coverage problem.

Abstract

This study investigated the typical performance of approximation algorithms known as belief propagation, the greedy algorithm, and linear-programming relaxation for maximum coverage problems in sparse biregular random graphs. After we used the cavity method for a corresponding hard-core lattice-gas model, results showed 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.