# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Convergence of the Non-Uniform Directed Physarum Model

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1906.07781.pdf

(Preprint), 687KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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.

Cite as: https://hdl.handle.net/21.11116/0000-0005-1DBA-A

##### 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.

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.