English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Physarum Multi-Commodity Flow Dynamics

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.

Item is

Files

show Files
hide Files
:
arXiv:2009.01498.pdf (Preprint), 2MB
Name:
arXiv:2009.01498.pdf
Description:
File downloaded from arXiv at 2020-10-07 10:52
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Bonifaci, Vincenzo1, Author
Facca, Enrico1, Author
Folz, Frederic1, Author
Karrenbauer, Andreas2, Author           
Kolev, Pavel2, Author           
Mehlhorn, Kurt2, Author           
Morigi, Giovanna1, Author
Shahkarami, Golnoosh2, Author           
Vermande, Quentin1, Author
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Neural and Evolutionary Computing, cs.NE
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2020-09-032020-09-232020
 Publication Status: Published online
 Pages: 22 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2009.01498
BibTex Citekey: Bonifaci_arXiv2009.01498
URI: https://arxiv.org/abs/2009.01498
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show