Math 466/566 -- Network Optimization

Course Description
Network flow problems form an important subclass of linear programming problems with applications to several areas such as chemistry, computer networking, engineering, public policy, scheduling, telecommunications, transportation, and many other areas. 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, and the multi-commodity flow problem. 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. Emphasis will be on powerful algorithm strategies and tools for rigorous analysis of algorithms. Several important data structures used in the implementations of the algorithms will be discussed. Apart from problems involving proofs (in homework and exams), there will be assignments in which the student will produce simple implementations of some of the algorithms (using MATLAB or a similar package). Animations of algorithms will also be presented in order to help the student in gaining a sound intuition about the analysis of network flow algorithms.

Announcements

Monday, August 23: Looks like the Bookie people misplaced the order for the text!
I've placed the order again today, and they said that the book should come to the store by
Thursday (Aug 26) or Friday (Aug 27).
Wednesday, September 15: I've added a list of errors/typos in the book (link above).
If you come across any errors, do pass them on to me.
I've listed the topics covered in each class till now (link above).
Friday, October 8: The solutions for all the homeworks handed out till now, and for the
practice midterm are up. There are minor changes to the solutions of problem 4 in
Homework 3 and problem 5 in homework 4.
I'll be attending a talk from 1:10-2:00 pm on Monday (Oct 11). Come to my office
any time after 11:00 am, or after 2:00 pm if you have questions.
Tuesday, October 19: The class average for the midterm exam is 78 / 100.

Handouts
Seat-sharing problem (PS FILE)
Flow decomposition algorithm (PS FILE)

Project (PS file) -- Due on Thursday, Dec 2.
Project Suggestions (PS FILE)
Solutions to problems in project (HW 10) (PS file)

Exams
Practice midterm    (PS file)
     Solutions to practice midterm (PS file)
Midterm    (PS file)
     Solutions to midterm (PS file)
Final Exam    (PS file) -- Due on Monday, Dec 13 at 5:00 pm.

MATLAB Codes
Example 1
netdata
BFS
dijkstra
Shortest augmenting path

Software
GIDEN

Last modified: Mon Aug 21 22:54:59 PDT 2006