hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Dynamical Systems, math.DS,Mathematics, Optimization and Control, math.OC, Physics, Biological Physics, physics.bio-ph
Abstract:
In this paper, we present two results on slime mold computations. The first
one treats a biologically-grounded model, originally proposed by biologists
analyzing the behavior of the slime mold Physarum polycephalum. This primitive
organism was empirically shown by Nakagaki et al. to solve shortest path
problems in wet-lab experiments (Nature'00). We show that the proposed simple
mathematical model actually generalizes to a much wider class of problems,
namely undirected linear programs with a non-negative cost vector.
For our second result, we consider the discretization of a
biologically-inspired model. This model is a directed variant of the
biologically-grounded one and was never claimed to describe the behavior of a
biological system. Straszak and Vishnoi showed that it can
$\epsilon$-approximately solve flow problems (SODA'16) and even general linear
programs with positive cost vector (ITCS'16) within a finite number of steps.
We give a refined convergence analysis that improves the dependence on
$\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a
step size that is independent of $\epsilon$. Furthermore, we show that the
dynamics can be initialized with a more general set of (infeasible) starting
points.
