| Abstract 摘要 | Evaluating performance of approximation algorithms for optimization problems has attracted researchers' interests for the last decades. Along with the worst-case performance, the typical-case performance averaged over randomized problems is important in terms of theoretical and practical aspects. The minimum vertex cover (min-VC) problem is a famous example of combinatorial optimization problems defined on a graph. Because it is difficult to solve the problem exactly, several approximations such as a leaf removal (LR) algorithm and linear programming (LP) relaxation are known. For randomized min-VCs on specific Erdos-Renyi random graphs, the typical accuracy of LR shows a phase transition at some critical average degree [1]. On the other hand, interestingly, statistical-mechanical analyses reveal that the replica symmetry in the spin-glass theory breaks at the same critical average degree [2]. These facts suggest that there are a nontrivial relation between the typical performance of approximation algorithms and the statistical-mechanical property of the randomized problems.
Recently, we have developed the statistical-mechanical analysis of LP for the min-VCs. It shows that, for the Erdos-Renyi random graphs, the typical accuracy of LP also exhibits a phase transition at the same critical threshold [3,4]. Moreover, considering the typical behavior of LP and LR for the min-VCs on arbitrary random graphs, we obtained three cases of a magnitude relation of the critical thresholds [5]. In this seminar, I will present the overview of our studies and discuss the relationship between typical performance of approximation algorithms and a statistical mechanical picture of combinatorial optimization problems.
[1] R. Karp and M. Sipser, in 22nd Annu. Symp. Foundations of Comp. Sci., 364 (1981).
[2] M. Weigt~and A. K. Hartmann, Phys. Rev. Lett. 84, 6118 (2000).
[3] S. Takabe and K. Hukushima, J. Phys. Soc. Jpn. 83, 043801 (2014).
[4] S. Takabe and K. Hukushima, Phys. Rev. E 93, 053308 (2016)
[5] S. Takabe and K. Hukushima, arXiv:1605.04679 (2016). |
