*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
