Effect of constraint relaxation on the minimum vertex cover problem in random graphs Aki Dote and Koji Hukushima,“Effect of constraint relaxation on the minimum vertex cover problem in random graphs”,Phys. Rev. E 109, 044304 – Published 5 April 2024https://doi.org/10.1103/PhysRevE.109.044304 これは、この３月に卒業した土手さんの研究成果です。例によって周辺解説をします。 最適化問題は統計力学から見ると絶対零度極限に相当するので、熱力学極限での最適化問題の性質はFu-Anderson以来多くの統計力学的研究があります(こういうところにも出てくるP.W.Andersonはすごい）。Kirkpatrick-Selmanがランダム化された制約充足問題であるrandom SA...