24 citations · 76 across the 15 of their papers we have counts for
14 papers · 1 filter
Algorithm Engineering of SSSP With Negative Edge Weights
Alejandro Cassis, Andreas Karrenbauer, André Nusser +1
Computing shortest paths is one of the most fundamental algorithmic graph problems. It is known since decades that this problem can be solved in near-linear time if all weights are…
Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices
Angikar Ghosal, Andreas Karrenbauer
We investigate structural properties of the binary rank of Kronecker powers of binary matrices, equivalently, the biclique partition numbers of the corresponding bipartite graphs.…
A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
Sophia Saller, Jana Koehler, Andreas Karrenbauer
The traveling salesman (or salesperson) problem, short TSP, is a problem of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP vari…
Improving Order with Queues
Andreas Karrenbauer, Kurt Mehlhorn, Pranabendu Misra +4
Given a sequence of numbers and parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that queues suffice to sort…
Physarum Inspired Dynamics to Solve Semi-Definite Programs
Yuan Gao, Hamidreza Kamkari, Andreas Karrenbauer +2
Physarum Polycephalum is a slime mold that can solve shortest path problems. A mathematical model based on Physarum's behavior, known as the Physarum Directed Dynamics, can solve p…
Improved Online Algorithm for Fractional Knapsack in the Random Order Model
Jeff Giliberti, Andreas Karrenbauer
The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online s…
Reading Articles Online
Andreas Karrenbauer, Elizaveta Kovalevskaya
We study the online problem of reading articles that are listed in an aggregated form in a dynamic stream, e.g., in news feeds, as abbreviated social media posts, or in the daily u…
Physarum-Inspired Multi-Commodity Flow Dynamics
Vincenzo Bonifaci, Enrico Facca, Frederic Folz +6
In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks. For the shortest path pr…
Convergence of the Non-Uniform Physarum Dynamics
Andreas Karrenbauer, Pavel Kolev, Kurt Mehlhorn
Let , , and . We show under fairly general conditions that the non-uniform Physarum dynamics \[ \dot{x}_…
Two Results on Slime Mold Computations
Ruben Becker, Vincenzo Bonifaci, Andreas Karrenbauer +2
We present two results on slime mold computations. In wet-lab experiments (Nature'00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shor…
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…
Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
Ruben Becker, Sebastian Forster, Andreas Karrenbauer +1
We present a method for solving the transshipment problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of in undirected graphs w…
Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn +2
We present a near-optimal distributed algorithm for -approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+ \sqrt{n})\cdot n^{o(…
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…