1 citations · 1 across the 3 of their papers we have counts for
4 papers
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…
Smoothed Analysis of the Successive Shortest Path Algorithm
Tobias Brunsch, Kamiel Cornelissen, Bodo Manthey +2
The minimum-cost flow problem is a classic problem in combinatorial optimization with various applications. Several pseudo-polynomial, polynomial, and strongly polynomial algorithm…
Approximability of Connected Factors
Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey +2
Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte's reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal…
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…