1 citations · 1 across the 5 of their papers we have counts for
7 papers
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…
Solving Totally Unimodular LPs with the Shadow Vertex Algorithm
Tobias Brunsch, Anna Großwendt, Heiko Röglin
We show that the shadow vertex simplex algorithm can be used to solve linear programs in strongly polynomial time with respect to the number of variables, the number of con…
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^…
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…
Improved Smoothed Analysis of Multiobjective Optimization
Tobias Brunsch, Heiko Röglin
We present several new results about smoothed analysis of multiobjective optimization problems. Motivated by the discrepancy between worst-case analysis and practical experience, t…
Smoothed Performance Guarantees for Local Search
Tobias Brunsch, Heiko Röglin, Cyriel Rutten +1
We study popular local search and greedy algorithms for scheduling. The performance guarantee of these algorithms is well understood, but the worst-case lower bounds seem somewhat…
Lower Bounds for the Smoothed Number of Pareto optimal Solutions
Tobias Brunsch, Heiko Roeglin
In 2009, Roeglin and Teng showed that the smoothed number of Pareto optimal solutions of linear multi-criteria optimization problems is polynomially bounded in the number of va…