On the Convergence Time of a Natural Dynamics for Linear Programming

the solution of linear programming (LP) problems that was first proposed
in the mathematical biology literature as a model for the foraging
behavior of acellular slime mold Physarum polycephalum, and more
recently considered as a method to solve LPs. We study the convergence
time of the continuous Physarum dynamics in the context of the linear
programming problem, and derive a new time bound to approximate
optimality that depends on the relative entropy between projected
versions of the optimal point and of the initial point. The bound scales
logarithmically with the LP cost coefficients and linearly with the
inverse of the relative accuracy, establishing the efficiency of the
dynamics for arbitrary LP instances with positive costs.