GEORGE
MASON UNIVERSITY
School of Information
Technology and Engineering
Department of Systems
Engineering and Operations Research
Place & Time: S&T II, Room 128; Monday, 7:20 – 10:00
Instructor: Don Wagner
Telephone:
703-993-3806 / 703-696-4313
Email:
dwagner@gmu.edu
Office: S&T II, Room 112 (generally available on
Fridays)
Office Hours: By appointment
Text: Combinatorial Optimization by W. J.
Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, John Wiley &
Sons, 1998
Description: A rigorous
treatment of classic problems in combinatorial optimization,
focusing on algorithms and
associated polyhedral theory
Prerequisites: Linear programming, integer programming, and network
flows
Course Outline: Introduction Chapter
1
Minimum
Spanning Tree Problem Chapter
2
Kruskal’s
Algorithm
Spanning
Tree Polytope
Review of
Shortest Paths and Maximum Flows Chapters
2-3
Minimum-Cost
Flows Chapter
4
Primal
Algorithms
Dual
Algorithms
Matchings Chapter
5
Cardinality
Matching Algorithm
Weighted
Matching Algorithm
Matching
Polytope
Postman
problems
Possible additional topics:
Integrality of Polyhedra Chapter
6
Primal-Dual
Approximation Algorithms
Grading: Grades will be determined by 5-6 homework sets
distributed throughout the semester.
All work is to be done
independently.