event
Fast gradient methods for network flow problems
Primary tabs
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.
Status
- Workflow Status: Published
- Created By: Anita Race
- Created: 10/12/2009
- Modified By: Fletcher Moore
- Modified: 10/07/2016
Categories
Keywords
Target Audience