@article{BBKKM2018,
TITLE = {Two Results on Slime Mold Computations},
AUTHOR = {Becker, Ruben and Bonifaci, Vincenzo and Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt},
LANGUAGE = {eng},
ISSN = {0304-3975},
DOI = {10.1016/j.tcs.2018.08.027},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2019},
DATE = {2019},
ABSTRACT = {In this paper, we present two results on slime mold computations. The first<br>one treats a biologically-grounded model, originally proposed by biologists<br>analyzing the behavior of the slime mold Physarum polycephalum. This primitive<br>organism was empirically shown by Nakagaki et al. to solve shortest path<br>problems in wet-lab experiments (Nature'00). We show that the proposed simple<br>mathematical model actually generalizes to a much wider class of problems,<br>namely undirected linear programs with a non-negative cost vector.<br> For our second result, we consider the discretization of a<br>biologically-inspired model. This model is a directed variant of the<br>biologically-grounded one and was never claimed to describe the behavior of a<br>biological system. Straszak and Vishnoi showed that it can<br>$\epsilon$-approximately solve flow problems (SODA'16) and even general linear<br>programs with positive cost vector (ITCS'16) within a finite number of steps.<br>We give a refined convergence analysis that improves the dependence on<br>$\epsilon$ from polynomial to logarithmic and simultaneously allows to choose a<br>step size that is independent of $\epsilon$. Furthermore, we show that the<br>dynamics can be initialized with a more general set of (infeasible) starting<br>points.<br>},
JOURNAL = {Theoretical Computer Science},
VOLUME = {773},
PAGES = {79--106},
}