Math 409

Math 409
Discrete Optimization



Math 409 is a discrete optimization course covering classical topics of spanning trees, shortest paths, flows, total unimodularity, the Branch & Bound algorithm, matchings in non-bipartite graphs and approximation algorithms. This is a proof-based class. We introduce problems and algorithms, but the emphasis is on revealing structural properties and proving correctness, not on implementation details such as data structures.

Prerequisits: Formally a minimum grade of 2.0 in Math 407; and either a minimum
grade of 2.0 in Math 300, or a minimum grade of 2.0 in Math 334. Effectively, knowledge of linear algebra and some understanding of algorithms is needed.

Sample syllabus:

Chapter 1 - Introduction
  • Algorithms & running times
  • Graphs
  • TSP
Chapter 2 - Spanning trees
  • Spanning trees
  • Kruskal's algorithm
Chapter 3 - Shortest paths
  • Dijkstra's algorithm
  • The Moore-Bellman-Ford algorithm
  • Node potentials
Chapter 4 - Network flows
  • The maximum s-t flow problem
  • Residual graphs
  • Ford-Fulkerson algorithm
  • The MinCut problem
  • MaxFlow=MinCut Theorem
  • The Edmonds-Karp algorithm
  • Matchings in bipartite graphs; Koenig's Theorem and Halls' Theorem
Chapter 5 - Linear programming
  • Convexity, polyhedra
  • Separation
  • Farkas Lemma
  • The Strong Duality Theorem
  • Integer programs and integer hulls
Chapter 6 - Total unimodularity
  • The concept of total unimodularity
  • Proof that TU constraint matrix implies extreme points are integer
  • Application to bipartite matching (node edge matrices of undirected graphs)
  • Application to flows (node-edge incidence matrices of directed graphs)
  • Application to interval scheduling (matrices with consecutive ones)
Chapter 7 - Branch & Bound
  • The Branch & Bound algorithm
  • Different strategies and a pathological instance
Chapter 8 - Non-bipartite matching
  • Augmenting paths
  • Computing Augmenting paths
  • Odd cycles and flowers
  • Edmonds' Blossom algorithm
Chapter 9 - Knapsack
  • Dynamic program for Knapsack
  • An approximation algorithm for Knapsack