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. |