Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On the Convergence Time of a Natural Dynamics for Linear Programming
Speaker:Vincenzo Bonifaci
coming from:IASI-CNR
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 14 February 2017
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4 - MPI-INF
Room:024
Abstract
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.

Contact
Name(s):Emanuele Natale
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Emanuele Natale, 01/12/2017 02:10 PMLast modified by:Uwe Brahm/MPII/DE, 02/14/2017 04:01 AM
  • Emanuele Natale, 01/12/2017 02:12 PM
  • Emanuele Natale, 01/12/2017 02:10 PM -- Created document.