2 papers
cs.DS2015
Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm
Kamiel Cornelissen, Bodo Manthey
The minimum-cost flow (MCF) problem is a fundamental optimization problem with many applications and seems to be well understood. Over the last half century many algorithms have be…
cs.DS2012
Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +1
Belief propagation (BP) is a message-passing heuristic for statistical inference in graphical models such as Bayesian networks and Markov random fields. BP is used to compute margi…