Network Optimization - Math 466/566

Math 566  - Network Optimization

Course Description
Network flow problems form an important class of optimization problems, with applications to several areas including chemistry, computer networking, engineering, public policy, scheduling, telecommunications, transportation, and more recently, big data analytics. This course will provide 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. Limited use of a linear programming approach will be involved, for which the necessary background materials will be reviewed. Previous knowledge of linear optimization will not be required. The only (pre)requirement is mathematical sophistication and intuition! Emphasis will be on 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 simple implementations of some of the algorithms (using Octave/Matlab or Python, or a similar package/language). Depending on student interest, we will discuss specific applications and topics from data sciences and/or combinatorial optimization.

Syllabus and Schedule  
Some options to buy the text (search the web to find more options!)

Announcements

Thu, Sep 15: Lectures on Tuesday (9/20) and Thursday (9/22) will originate in Pullman.
Fri, Sep 16: Homework scores are now posted against PassNumbers (under the Homework tab).
Fri, Sep 30: No regular lecture on Tuesday, Oct 4. Instead, a review lecture is already posted.
Tue, Oct 04: Office hours on Skype this week are Oct 4: 10:45 AM-noon, 2-3 PM; Oct 5: 10 AM-noon.
Wed, Dec 07: Regular lecture is canceled for tomorrow (Dec 8). A video lecture will be posted instead.


Submit feedback!!   (click it)


Last modified: Wed Dec 07 22:46:12 PST 2016