|
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 (at the level
of Math364, in
particular) 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).
|