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

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

Bodo Manthey, Heiko Röglin, 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

68W40: Analysis of algorithms

90C27: Combinatorial optimization

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)