3 citations
5 papers
An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions
Ruben Becker, Andreas Karrenbauer, Kurt Mehlhorn
We present an interior point method for the min-cost flow problem that uses arc contractions and deletions to steer clear from the boundary of the polytope when path-following meth…
A Combinatorial -time Algorithm for the Min-Cost Flow Problem
Ruben Becker, Andreas Karrenbauer
We present a combinatorial method for the min-cost flow problem and prove that its expected running time is bounded by . This matches the best known bounds, whic…
Distributed computation of persistent homology
Ulrich Bauer, Michael Kerber, Jan Reininghaus
Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation…
Approximate Cech Complexes in Low and High Dimensions
Michael Kerber, R. Sharathkumar
Čech complexes reveal valuable topological information about point sets at a certain scale in arbitrary dimensions, but the sheer size of these complexes limits their practical imp…
Embedding the dual complex of hyper-rectangular partitions
Michael Kerber
A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a "nice" drawing of its du…