CMPUT 670
Topics in the Theory of Computation: Combinatorial Optimization
fall 2001
MWF 1300-1350, CSC B41, Instructor: Ryan Hayward
purpose
a graduate level introduction to combinatorial optimization
prerequisites
a strong background in algorithms and discrete math
the course will follow selected parts of the text
grading
quizzes 30%
homework 55%
project 15%
text
Combinatorial Optimization
W.Cook, W. Cunningham, W. Pulleyblank, A. Schrijver
1998 John Wiley & Sons
ISBN 0-471-55894-X
- problems/algorithms
- optimal trees/paths
- max flow
- min-cost flow
- optimal matchings
- integrality of polyhedra
- traveling salesperson problem
- matroids
- NP-completeness