0

(

ratings

)

1

students

Created by:

Profile Photo

Last updated:

September 20, 2022

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description

15.082J/6.855J/ESD.78J is a graduate subject in the theory and practice of network flows and its extensions.

Network flow problems form a subclass of linear programming problems with applications to transportation, logistics, manufacturing, computer science, project management, and finance, as well as a number of other domains. This subject will survey some of the applications of network flows and focus on key special cases of network flow problems including the following: the shortest path problem, the maximum flow problem, the minimum cost flow problem, and the multi-commodity flow problem. We will also consider other extensions of network flow problems.

Course Curriculum

  • Introduction to network models Unlimited
  • Computational complexity and data structures Unlimited
  • Graph search algorithms Unlimited
  • Transformations and flow decomposition Unlimited
  • Shortest paths: label setting algorithms Unlimited
  • The radix heap algorithm Unlimited
  • Shortest paths: label correcting algorithms Unlimited
  • Algorithm analysis Unlimited
  • Basic algorithms for the maximum flow problem Unlimited
  • Combinatorial applications of maximum flows Unlimited
  • Preflow push algorithms Unlimited
  • More on preflow push algorithms Unlimited
  • Minimum cost flow: basic algorithms Unlimited
  • Minimum cost flow: polynomial time algorithms Unlimited
  • Applications of network flows; Linear programming review Unlimited
  • The network simplex algorithm Unlimited
  • Lagrangian relaxation 1 Unlimited
  • Lagrangian relaxation 2 Unlimited
  • Multicommodity flows 1 Unlimited
  • Multicommodity flows 2 Unlimited

About the instructor

5 5

Instructor Rating

1

Reviews

1520

Courses

1916

Students

Profile Photo
Massachusetts Institute of Technology