Typical performance of approximation algorithms for NP-hard problems. (9th November 2016)

• Record Type: Journal Article
• Authors: Takabe, Satoshi; Hukushima, Koji
• Is Part Of: Journal of statistical mechanics. (2016:Nov.)
• Publication Date: 2016-11-09
• Subjects: 11 -- 7; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/2016/11/113401
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: 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 the presentation of a theoretical framework. Herein, three approximation algorithms are examined: linear-programming relaxation, loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using a statistical–mechanical technique, whereas the average-case analysis of the last one is conducted using the generating function method. These algorithms have a threshold in the typical performance with increasing 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. In addition, we provide some conditions for classification of the graph ensembles and demonstrate explicitly some examples for the difference in thresholds.