UC Berkeley
IEOR Department
IEOR
266
NETWORK
FLOWS AND GRAPHS
Fall
2003
|
|
|
Time: TTH 3:30-5:00
Place: 3113 Etcheverry Hall
Prerequisite: IEOR 262A
3 Units
|
|
Office: 4181 Etcheverry Hall
Office Hours: Thu 12-1pm
|
|
Phone: 642 - 4998
|
|
e-mail:mailto:hochbaum@ieor.berkeley.edu
|
Reader: No one
so far (you will have to grade your own assignments)
|
|
e-mail:
|
Course Topics
- Course Introduction:
definitions of graphs and algorithms
- The concept of running time
and complexity of algorithms
- Special cases of the minimum
cost flow problem: The assignment problem, the transportation problem,
shortest path problem, longest path for CPM and project management,
maximum flow problem. Applications in production, inventory control and
planning. Formulation of problems as network flow problems.
- Shortest path algorithms. Bellman-Ford,
Dijkstra (for nonnegative costs); all-pairs algorithms, Floyd-Warshall,
D.B. Johnson's.
- The maximum flow min-cut
theorem.
- The Ford-Fulkerson algorithm.
- Applications of maximum flow
and of minimum cut.
- The history of algorithms for
the maximum flow problem. Polynomial algorithms for maximum flows –Dinic’s
Goldberg’s Hochbaum’s.
- Matching problems (bipartite
and nonbipartite.)
- The minimum cost network flow
problem. Relationship to linear programming.
- Totally unimodular matrices.
- Vertex cover and independent
set on bipartite graphs. Applications in covering and packing.
- Eulerian graphs. The Chinese
postman problem. Traveling salesperson problem.
- The assignment problem.
Concept of the primal-dual approach.
- Minimum spanning tree
problem. Applications.
- Connectivity problems.
- Planar graphs.
- Related NP-hard problems:
Vertex disjoint paths, Hamiltonian circuit and traveling salesperson
problem, maximum clique problem, colorability problem, multicommodity
problem, location problems, bin packing.
- Approximation algorithms.
Assignments
All assignments are
available in postscript format which can be downloaded and viewed by
a proper software package such as GhostView.
Scribe Notes
While course material may be slightly different this year than in years past,
these notes may prove helpful as a supplemental resource. You may download them
as references to help you learn the materials given in the lecture.
Postscript lecture notes
taken by class members in Spring 1995.
Postscript lecture
notes taken by class members and updated by Prof Hochbaum in Fall 2000.
You are encouraged to submit the scribe notes in LaTeX. A tutorial for LaTeX
can be found in http://www.stat.berkeley.edu/users/spector
Last update: August 24, 2003