Math 466/566:  Network Optimization

Course Overview

Welcome to Network Optimization! We will present an integrated view of the theory, algorithms, and the applications of key network optimization problems including the shortest path problem, the maximum flow problem, the minimum cost flow problem, the minimum spanning tree problem, and matching problems. Most of the arguments will be presented from first principles, and we will adopt a network or graphical view point. Previous knowledge of linear optimization will not be required. We will emphasize powerful algorithm strategies, rigorous analysis of the algorithms, and data structures for their implementation. Apart from problems involving proofs (in homework and the midterm exam), the student will be produce implementations of some of the algorithms (using Matlab; or Python or a similar package/language).