English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Physarum Multi-Commodity Flow Dynamics

MPS-Authors
/persons/resource/persons44737

Karrenbauer,  Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons136381

Kolev,  Pavel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons251338

Shahkarami,  Golnoosh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)

arXiv:2009.01498.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bonifaci, V., Facca, E., Folz, F., Karrenbauer, A., Kolev, P., Mehlhorn, K., et al. (2020). Physarum Multi-Commodity Flow Dynamics. Retrieved from https://arxiv.org/abs/2009.01498.


Cite as: http://hdl.handle.net/21.11116/0000-0007-2312-D
Abstract
In wet-lab experiments \cite{Nakagaki-Yamada-Toth,Tero-Takagi-etal}, the slime mold Physarum polycephalum has demonstrated its ability to solve shortest path problems and to design efficient networks, see Figure \ref{Wet-Lab Experiments} for illustrations. Physarum polycephalum is a slime mold in the Mycetozoa group. For the shortest path problem, a mathematical model for the evolution of the slime was proposed in \cite{Tero-Kobayashi-Nakagaki} and its biological relevance was argued. The model was shown to solve shortest path problems, first in computer simulations and then by mathematical proof. It was later shown that the slime mold dynamics can solve more general linear programs and that many variants of the dynamics have similar convergence behavior. 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.