Campus Event Calendar

Event Entry

What and Who

On the Convergence Time of a Natural Dynamics for Linear Programming

Vincenzo Bonifaci
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 14 February 2017
30 Minutes
E1 4 - MPI-INF


We consider a system of nonlinear ordinary differential equations for

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.


Emanuele Natale
--email hidden
passcode not visible
logged in users only

Emanuele Natale, 01/12/2017 14:12
Emanuele Natale, 01/12/2017 14:10 -- Created document.