English

Item

ITEM ACTIONSEXPORT

Convergence of the Non-Uniform Directed Physarum Model

Facca, E., Karrenbauer, A., Kolev, P., & Mehlhorn, K. (2019). Convergence of the Non-Uniform Directed Physarum Model. Retrieved from http://arxiv.org/abs/1906.07781.

Item is

show hide
Genre: Paper

Files

show Files
hide Files
:
arXiv:1906.07781.pdf (Preprint), 687KB
Name:
arXiv:1906.07781.pdf
Description:
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
-
-

show

Creators

show
hide
Creators:
Facca, Enrico1, Author
Karrenbauer, Andreas2, Author
Kolev, Pavel2, Author
Mehlhorn, Kurt2, Author
Affiliations:
1External Organizations, ou_persistent22
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show
hide
Free keywords: Mathematics, Dynamical Systems, math.DS,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Optimization and Control, math.OC
Abstract: The directed Physarum dynamics is known to solve positive linear programs:
minimize $c^T x$ subject to $Ax = b$ and $x \ge 0$ for a positive cost vector
$c$. The directed Physarum dynamics evolves a positive vector $x$ according to
the dynamics $\dot{x} = q(x) - x$. Here $q(x)$ is the solution to $Af = b$ that
minimizes the "energy" $\sum_i c_i f_i^2/x_i$.
In this paper, we study the non-uniform directed dynamics $\dot{x} = D(q(x) - x)$, where $D$ is a positive diagonal matrix. The non-uniform dynamics is more
complex than the uniform dynamics (with $D$ being the identity matrix), as it
allows each component of $x$ to react with different speed to the differences
between $q(x)$ and $x$. Our contribution is to show that the non-uniform
directed dynamics solves positive linear programs.

Details

show
hide
Language(s): eng - English
Dates: 2019-06-182019
Publication Status: Published online
Pages: 14 p.
Publishing info: -
Rev. Type: -
Identifiers: arXiv: 1906.07781
URI: http://arxiv.org/abs/1906.07781
BibTex Citekey: Facca_arXiv1906.07781
Degree: -

show

show

show

show