TITLE: Fast gradient methods for network flow problems

SPEAKER: Dr. Yuri Nesterov

ABSTRACT:

In this talk we present a new approach for finding approximate solutions to different network problems related to multi-commodity flows. We consider simple subgradient schemes and schemes based on the smoothing technique. The fastest of our methods solves the maximal concurrent flow problem in $O({qm ln n over delta})$ iterations, where $delta$ is the related accuracy, $m$ and $n$ are the number of arcs/nodes in the graph, and $q$ is the number
of commodity sources. Each iteration of these schemes is very simple and does not require any sophisticated operations (e.g. shortest path computation). Its complexity is of the order $O(mq ln q)$ operations. The application of our approach needs a preliminary computational stage
consisting in finding all node-to-node maximal flows, which takes $O(n2 m ln n)$ operations.