Author name cluster

Andreas Karrenbauer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

TCS Journal 2022 Journal Article

Physarum-inspired multi-commodity flow dynamics

Vincenzo Bonifaci
Enrico Facca
Frederic Folz
Andreas Karrenbauer
Pavel Kolev
Kurt Mehlhorn
Giovanna Morigi
Golnoosh Shahkarami

In wet-lab experiments, the slime mold Physarum polycephalum has demonstrated its ability to tackle a variety of computing tasks, among them the computation of shortest paths and the design of efficient networks. For the shortest path problem, a mathematical model for the evolution of the slime is available and it has been shown in computer experiments and through mathematical analysis that the dynamics solves the shortest path problem. In this paper, we generalize the dynamics to the network design problem. We formulate network design as the problem of constructing a network that efficiently supports a multi-commodity flow problem. We investigate the dynamics in computer simulations and analytically. The simulations show that the dynamics is able to construct efficient and elegant networks. In the theoretical part we show that the dynamics minimizes an objective combining the cost of the network and the cost of routing the demands through the network. We also give alternative characterizations of the optimum solution.

Details DOI

TCS Journal 2020 Journal Article

Convergence of the non-uniform directed Physarum model

Enrico Facca
Andreas Karrenbauer
Pavel Kolev
Kurt Mehlhorn

The directed Physarum dynamics is known to solve positive linear programs: minimize c T x subject to A x = b and x ≥ 0 for a positive cost vector c. The directed Physarum dynamics evolves a positive vector x according to the dynamics x ˙ = q ( x ) − x. Here q ( x ) is the solution to A f = b that minimizes the “energy” ∑ i c i f i 2 / x i. In this paper, we study the non-uniform directed dynamics x ˙ = D ( q ( x ) − x ), where D is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with D being the identity matrix), as it allows each component of x to react with different speed to the differences between q ( x ) and x. Our contribution is to show that the non-uniform directed dynamics solves positive linear programs.

Details DOI

TCS Journal 2020 Journal Article

Convergence of the non-uniform Physarum dynamics

Andreas Karrenbauer
Pavel Kolev
Kurt Mehlhorn

The Physarum computing model is an analog computing model motivated by the network dynamics of the slime mold Physarum Polycephalum. In previous works, it was shown that it can solve a class of linear programs. We extend these results to a more general dynamics motivated by situations where the slime mold operates in a non-uniform environment. Let c ∈ Z > 0 m, A ∈ Z n × m, and b ∈ Z n. We show under fairly general conditions that the non-uniform Physarum dynamics x ˙ e = a e ( x, t ) ( | q e | − x e ) converges to the optimum solution x ⁎ of the weighted basis pursuit problem minimize c T x subject to A f = b and | f | ≤ x. Here, f and x are m-dimensional vectors of real variables, q minimizes the energy ∑ e ( c e / x e ) q e 2 subject to the constraints A q = b and supp ( q ) ⊆ supp ( x ), and a e ( x, t ) > 0 is the reactivity of edge e to the difference | q e | − x e at time t and in state x. Previously convergence was only shown for the uniform case a e ( x, t ) = 1 for all e, x, and t. We also show convergence for the dynamics x ˙ e = x e ( g e ( | q e | x e ) − 1 ), where each g e is an increasing differentiable function with g e ( 1 ) = 1 (satisfying some mild conditions). Previously, convergence was only shown for the special case of the shortest path problem on a graph consisting of two nodes connected by parallel edges.

Details DOI

TCS Journal 2019 Journal Article

Two results on slime mold computations

Ruben Becker
Vincenzo Bonifaci
Andreas Karrenbauer
Pavel Kolev
Kurt Mehlhorn

We present two results on slime mold computations. In wet-lab experiments by Nakagaki et al. (2000) [1] the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system of differential equations, for the slime's adaption process (Tero et al. , 2007) [3]. It was shown that the process convergences to the shortest path (Bonifaci et al. , 2012) [5] for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. Combinatorial optimization researchers took the dynamics describing slime behavior as an inspiration for an optimization method and showed that its discretization can ε-approximately solve linear programs with positive cost vector (Straszak and Vishnoi, 2016) [14]. Their analysis requires a feasible starting point, a step size depending linearly on ε, and a number of steps with quartic dependence on opt / ( ε Φ ), where Φ is the difference between the smallest cost of a non-optimal basic feasible solution and the optimal cost (opt). We give a refined analysis showing that the dynamics initialized with any strongly dominating point converges to the set of optimal solutions. Moreover, we strengthen the convergence rate bounds and prove that the step size is independent of ε, and the number of steps depends logarithmically on 1 / ε and quadratically on opt / Φ.

Details DOI

ICML Conference 2018 Conference Paper

Partial Optimality and Fast Lower Bounds for Weighted Correlation Clustering

Jan-Hendrik Lange
Andreas Karrenbauer
Bjoern Andres

Weighted correlation clustering is hard to solve and hard to approximate for general graphs. Its applications in network analysis and computer vision call for efficient algorithms. To this end, we make three contributions: We establish partial optimality conditions that can be checked efficiently, and doing so recursively solves the problem for series-parallel graphs to optimality, in linear time. We exploit the packing dual of the problem to compute a heuristic, but non-trivial lower bound faster than that of a canonical linear program relaxation. We introduce a re-weighting with the dual solution by which efficient local search algorithms converge to better feasible solutions. The effectiveness of our methods is demonstrated empirically on a number of benchmark instances.

Details

SAT Conference 2017 Conference Paper

From DQBF to QBF by Dependency Elimination

Ralf Wimmer 0001
Andreas Karrenbauer
Ruben Becker
Christoph Scholl 0001
Bernd Becker 0001

Abstract In this paper, we propose the elimination of dependencies to convert a given dependency quantified Boolean formula (DQBF) to an equisatisfiable QBF. We show how to select a set of dependencies to eliminate such that we arrive at a smallest equisatisfiable QBF in terms of existential variables that is achievable using dependency elimination. This approach is improved by taking so-called don’t-care dependencies into account, which result from the application of dependency schemes to the formula and can be added to or removed from the formula at no cost. We have implemented this new method in the state-of-the-art DQBF solver HQS. Experiments show that dependency elimination is clearly superior to the previous method using variable elimination.

Details

TCS Journal 2015 Journal Article

The interval constrained 3-coloring problem

Jaroslaw Byrka
Andreas Karrenbauer
Laura Sanità

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. We also show that it is hard to satisfy almost all of the constraints for a feasible instance (even in the restricted case where each interval is used at most once). This implies APX-hardness of maximizing the number of simultaneously satisfiable intervals.

Details DOI