Current browse context:
physics.soc-ph
Change to browse by:
References & Citations
Physics > Physics and Society
Title: Fast convergence to an approximate solution by message-passing for complex optimizations
(Submitted on 19 Dec 2023 (v1), last revised 2 Apr 2024 (this version, v2))
Abstract: Message-passing (MP) is a powerful tool for finding an approximate solution in optimization. We generalize it to nonlinear product-sum form, and numerically show the fast convergence for the minimum feedback vertex set and the minimum vertex cover known as NP-hard problems. From the linearity of MP in a logarithmic space, it is derived that an equilibrium solution exists in a neighborhood of random initial values. These results will give one of the reason why the convergence is very fast in collective computation based on a common mathematical background.
Submission history
From: Yukio Hayashi [view email][v1] Tue, 19 Dec 2023 07:34:49 GMT (993kb)
[v2] Tue, 2 Apr 2024 04:55:40 GMT (993kb)
Link back to: arXiv, form interface, contact.