MA5211: Discrete Optimization
Text
W. Kocay and D.L. Kreher , Graphs, Algorithms, and Optimization , Chapman \&
Hall/CRC Press , Boca Raton, Florida, 2005.
Course Descrition.
MA 5211 - Discrete Optimization Optimization problems (traveling salesman, minimal spanning tree, linear programming, scheduling, etc.), simplex algorithm, primal-dual algorithms, complexity,
matching, weighted matching, spanning trees, matroid theory, integer linear programming, approximation algorithms, branch-and-bound, local search, polyhedral theory.
Syllabus
We will discuss the following topics:
-
Basic graph algorithms.
-
Linear programming and duality theory
emphasizing network flow.
-
Integer linear programming.
Grading
Your grade will be based on 2 or 3 take home examinations.
a final examination.
Start every written assignment at the top of a
new page, put your name at the beginning of each page and do not staple
different problems together. I expect the problems to be well written
in full English sentences with no gaps in detail or logic. Please
be as elegant and as concise as possible. Cite all references.
pivot