everything.study
ESD.78

Network Optimization

Graduate · Historical course

Fall 2010

Topics

  • Introduction to network models
  • Computational complexity and data structures
  • Graph search algorithms
  • Transformations and flow decomposition
  • Shortest paths: label setting algorithms
  • The radix heap algorithm
  • Shortest paths: label correcting algorithms
  • Algorithm analysis
  • Basic algorithms for the maximum flow problem
  • Midterm 1 (Ses #1-8)
  • Combinatorial applications of maximum flows
  • Preflow push algorithms
  • More on preflow push algorithms
  • Minimum cost flow: basic algorithms
  • Minimum cost flow: polynomial time algorithms
  • Applications of network flows; Linear programming review
  • The network simplex algorithm
  • NP-completeness
  • Midterm 2 (Ses #9-17)
  • Lagrangian relaxation 1
  • Lagrangian relaxation 2
  • Multicommodity flows 1
  • Multicommodity flows 2
  • Presentations of class projects
  • Presentations of class projects (cont.)

Readings

  • Ahuja, Ravindra K., Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications . Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 9780136175490.
    Listed reading
Sources