CSE 523: Computational Geometry
Spring 1999
Richard Anderson

Topic

The topic of the course will NOT be computational geometry, it will be combinatorial optimization. The plan for this course has always been to present a set of advanced topics relating to the network flow problem.

Personnel

Name Email Office Hours
Instructor Richard Anderson anderson@cs.washington.edu By appointment, Sieg 312


Schedule

Lectures: TTh 12:00-1:20, Mue 153 (Mueller Hall)


The Mailing List

To subscribe to the mailing list, send email to majordomo@cs with an empty subject line and the text

subscribe cse523

as the body of the message. The address of the mailing list is cse523@cs. Do not send subscription requests to the list itself.


Text Book

The text for the course is the book, Network Flows, by Ahuja, Magnanti, and Orlin. It is an excellent (but expensive book). Available in the bookstore.

Topics

1. Maximum Flows: Basic ideas
	Maxflow/mincut theorem
	Generic Augmentation Algorithm

2. Polynomial Algorithms:
	Capacity Scaling
	Shortest Augmenting Path Algorithm
	Dinics Algoirthm
	Efficient Data Structures, Dynamic Trees

3. Preflow Push Algorithms:
	Generic Preflow Push Algorithm
	FIFO Algorithm
	Highest Level First Algorithm
	Rao/Golberg Algorithm

4. Empirical and Average Case Results

5. Special Cases
	Unit Capacity Networks
	Bipartite Networks
	Planar Networks

6. Matching
	Non-bipartite Matching
	Determinant Tricks

7. Mincost Flow (edges have costs as well as capacities)
	Basic Algorithms
	Polynomial Time Algorithms
	Network Simplex
	Minimum Weight Matching

8. Generalized Flows (edges have multipliers which change quantity of flow).
	Linear Programming Solutions
	Combinatorial Approaches

9. Multicommodity Flow (different types of flows along edges)
	

Content, Evaluation, Homework, Exams

If you have questions about the coruse, please contact me.


cse321-request@cs.washington.edu And now, cse 598! (Last Update: 08/05/99 )