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/Φ.

Becker, R., Bonifaci, V., Karrenbauer, A., Kolev, P., & Mehlhorn, K. (2019). Two results on slime mold computations. THEORETICAL COMPUTER SCIENCE, 773, 79-106 [10.1016/j.tcs.2018.08.027].

Two results on slime mold computations

Bonifaci V.;
2019

Abstract

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/Φ.
Becker, R., Bonifaci, V., Karrenbauer, A., Kolev, P., & Mehlhorn, K. (2019). Two results on slime mold computations. THEORETICAL COMPUTER SCIENCE, 773, 79-106 [10.1016/j.tcs.2018.08.027].
File in questo prodotto:
File Dimensione Formato  
phys-2res-arxiv.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: DRM non definito
Dimensione 563.82 kB
Formato Adobe PDF
563.82 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/381913
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact