Technion, Israel Institute of Technology

May 04, 2009, 14:15, Room MA A1 12 (Bat. MA) (click here for the map)

## N-Fold Integer Programming and Multicommodity Flows

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.

[Download the slides here]