Natural Dynamics for Linear Programming

Inspired by computational abilities of the organism slime mold, several researchers have recently proposed dynamical systems aimed at solving fundamental problems such as min-cost flow and, more generally, linear programming. In this talk I will present these dynamics from an optimization viewpoint and show that they provably work. Together, these results shed some light on how nature might be solving instances of perhaps the most complex problem in P: linear programming.

This is based on joint works with Damian Straszak (EPFL).