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:
    1. Basic graph algorithms.
    2. Linear programming and duality theory emphasizing network flow.
    3. 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