everything.study
MATH 3802

Combinatorial Optimization

0.5 credit · Undergraduate

Network flow problems, network simplex method, max-flow min-cut problem, integral polyhedra, minimum-weight spanning tree problem, maximum matching problem, maximum stable set problem, introduction to approximation algorithms.

2021

Topics

  • 15 self-directed review of MATH 3801 material
  • 22 total unimodularity, integral polyhedra, directed graphs
  • 29 minimum-cost flow problem, integral flow, network simplex method
  • 5 finite termination of network simplex method
  • 12 maximum s-t flow, max-flow min-cut theorem
  • 5 undirected graphs, trees, forests, matchings
  • 12 minimum-weight spanning tree
  • 19 maximum-cardinality matching for bipartite graphs
  • 26 maximum-cardinality matching in general
  • Apr 2 maximum-cardinality stable set, stable set polytope
  • 9 approximation algorithms
  • projects due

Prerequisites & course information

Prerequisite(s): MATH 3801 or permission of the School. Lectures three hours a week, tutorial one hour a week.

Sources