Andreas Karrenbauer

Andreas Karrenbauer
Are you Andreas Karrenbauer?

Claim your profile, edit publications, add additional information:

Contact Details

Andreas Karrenbauer

Pubs By Year

Pub Categories

Computer Science - Data Structures and Algorithms (4)
Computer Science - Discrete Mathematics (2)
Mathematics - Optimization and Control (2)
Computer Science - Multimedia (1)
Computer Science - Cryptography and Security (1)
Computer Science - Distributed; Parallel; and Cluster Computing (1)
Mathematics - Numerical Analysis (1)
Computer Science - Computer Vision and Pattern Recognition (1)

Publications Authored By Andreas Karrenbauer

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 methods come too close. We obtain a randomized algorithm running in expected $\tilde O( m^{3/2} )$ time that only visits integer lattice points in the vicinity of the central path of the polytope. This enables us to use integer arithmetic like classical combinatorial algorithms typically do. Read More

We present a method for solving the shortest transshipmen} problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of $ 1 + \epsilon $ in undirected graphs with polynomially bounded integer edge weights using a tailored gradient descent algorithm. An important special case of the transshipment problem is the single-source shortest paths (SSSP) problem. Our gradient descent algorithm takes $ \epsilon^{-3} polylog{n} $ iterations, and in each iteration it needs to solve the transshipment problem up to a multiplicative error of $ polylog n $, where $ n $ is the number of nodes. Read More

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(1)}$ communication rounds in the \Congest model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tilde{\Omega}(D+ \sqrt{n})$ round complexity lower bound. Read More

We present a combinatorial method for the min-cost flow problem and prove that its expected running time is bounded by $\tilde O(m^{3/2})$. This matches the best known bounds, which previously have only been achieved by numerical algorithms or for special cases. Our contribution contains three parts that might be interesting in their own right: (1) We provide a construction of an equivalent auxiliary network and interior primal and dual points with potential $P_0=\tilde{O}(\sqrt{m})$ in linear time. Read More

We discuss a method for tracking individual molecules which globally optimizes the likelihood of the connections between molecule positions fast and with high reliability even for high spot densities and blinking molecules. Our method works with cost functions which can be freely chosen to combine costs for distances between spots in space and time and which can account for the reliability of positioning a molecule. To this end, we describe a top-down polyhedral approach to the problem of tracking many individual molecules. Read More

A general method for recovering missing DCT coefficients in DCT-transformed images is presented in this work. We model the DCT coefficients recovery problem as an optimization problem and recover all missing DCT coefficients via linear programming. The visual quality of the recovered image gradually decreases as the number of missing DCT coefficients increases. Read More

In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NP-complete if the number of different colors is 3. Previously, it has only been known that it is NP-complete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. Read More