Technion, Israel Institute of Technology
May 04, 2009, 14:15, Room MA A1 12 (Bat. MA) (click here for the map)
I will describe our recently developed theory of n-fold integer programming, which enables polynomial time solution of fundamental linear and nonlinear integer programming problems in variable dimension. I will demonstrate the power of this theory by deriving a polynomial time algorithm for multicommodity flow problems where the cost of flow over a channel is a more realistic, nonlinear, function of the flow, accounting for channel congestion under heavy traffic or communication load.