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 gen- eralizes 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 lin- ear programs with positive cost vector (ITCS'16) within a finite num- ber of steps. We give a refined convergence analysis that improves the dependence on epsilon from polynomial to logarithmic and simul- taneously 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.
Two results on slime mold computations
Bonifaci Vincenzo;
2017
Abstract
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 gen- eralizes 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 lin- ear programs with positive cost vector (ITCS'16) within a finite num- ber of steps. We give a refined convergence analysis that improves the dependence on epsilon from polynomial to logarithmic and simul- taneously 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
