Kurt Mehlhorn

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 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. We provide explicit bounds on the size of the numbers that appear during all computations. By presenting an integer arithmetic interior point algorithm we avoid the tediousness of floating point error analysis and achieve a method that is guaranteed to be free of any numerical issues. We thereby eliminate one of the drawbacks of numerical methods in contrast to combinatorial min-cost flow algorithms that still yield the most efficient implementations in practice, despite their inferior worst-case time complexity.

Vincenzo Bonifaci, Enrico Facca, Frederic Folz et al.

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 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 introduce a dynamics for 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 characterization of the optimum solution.

Mohammad Abdulaziz, Kurt Mehlhorn, Tobias Nipkow

The goal of the LEDA project was to build an easy-to-use and extendable library of correct and efficient data structures, graph algorithms and geometric algorithms. We report on the use of formal program verification to achieve an even higher level of trustworthiness. Specifically, we report on an ongoing and largely finished verification of the blossom-shrinking algorithm for maximum cardinality matching.

Peyman Afshani, Manindra Agrawal, Benjamin Doerr et al.

We study the query complexity of a permutation-based variant of the guessing game Mastermind. In this variant, the secret is a pair $(z,π)$ which consists of a binary string $z \in \{0,1\}^n$ and a permutation $π$ of $[n]$. The secret must be unveiled by asking queries of the form $x \in \{0,1\}^n$. For each such query, we are returned the score \[ f_{z,π}(x):= \max \{ i \in [0..n]\mid \forall j \leq i: z_{π(j)} = x_{π(j)}\}\,;\] i.e., the score of $x$ is the length of the longest common prefix of $x$ and $z$ with respect to the order imposed by $π$. The goal is to minimize the number of queries needed to identify $(z,π)$. This problem originates from the study of black-box optimization heuristics, where it is known as the \textsc{LeadingOnes} problem. In this work, we prove matching upper and lower bounds for the deterministic and randomized query complexity of this game, which are $Θ(n \log n)$ and $Θ(n \log \log n)$, respectively.