Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching

DOI10.1007/978-3-642-36065-7_18zbMath1379.68278arXiv1211.3299OpenAlexW2110281697MaRDI QIDQ4914447

Heiko Röglin, Bodo Manthey, Tobias Brunsch, Kamiel Cornelissen

Publication date: 12 April 2013

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.3299

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (2)

Convergence and correctness of belief propagation for the Chinese postman problem ⋮ Derandomizing Isolation in Space-Bounded Settings

This page was built for publication: Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching