@online{DBLP:journals/corr/abs-1901-07231,
TITLE = {Convergence of the Non-Uniform Physarum Dynamics},
AUTHOR = {Karrenbauer, Andreas and Kolev, Pavel and Mehlhorn, Kurt},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1901.07231},
EPRINT = {1901.07231},
EPRINTTYPE = {arXiv},
YEAR = {2019},
ABSTRACT = {Let $c \in \mathbb{Z}^m_{> 0}$, $A \in \mathbb{Z}^{n\times m}$, and $b \in<br>\mathbb{Z}^n$. We show under fairly general conditions that the non-uniform<br>Physarum dynamics \[ \dot{x}_e = a_e(x,t) \left(|q_e| -- x_e\right) \] converges<br>to the optimum solution $x^*$ of the weighted basis pursuit problem minimize<br>$c^T x$ subject to $A f = b$ and $|f| \le x$. Here, $f$ and $x$ are $m$-vectors<br>of real variables, $q$ minimizes the energy $\sum_e (c_e/x_e) q_e^2$ subject to<br>the constraints $A q = b$ and $\mathrm{supp}(q) \subseteq \mathrm{supp}(x)$,<br>and $a_e(x,t) > 0$ is the reactivity of edge $e$ to the difference $|q_e| -<br>x_e$ at time $t$ and in state $x$. Previously convergence was only shown for<br>the uniform case $a_e(x,t) = 1$ for all $e$, $x$, and $t$. We also show<br>convergence for the dynamics \[ \dot{x}_e = x_e \cdot \left( g_e<br>\left(\frac{|q_e|}{x_e}\right) -- 1\right),\] where $g_e$ is an increasing<br>differentiable function with $g_e(1) = 1$. Previously convergence was only<br>shown for the special case of the shortest path problem on a graph consisting<br>of two nodes connected by parallel edges.<br>},
}