Fast gradient methods for network flow problems

Primary tabs

TITLE: Fast gradient methods for network flow problems

SPEAKER: Dr. Yuri Nesterov


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.


  • Workflow Status: Published
  • Created By: Anita Race
  • Created: 10/12/2009
  • Modified By: Fletcher Moore
  • Modified: 10/07/2016


Target Audience