2 papers
cs.DS2013
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
Tobias Brunsch, Heiko Röglin
We show that the shadow vertex algorithm can be used to compute a short path between a given pair of vertices of a polytope P = {x : Ax \leq b} along the edges of P, where A \in R^…
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…