Discrete Optimization

Catalog description

Cat. IIDiscrete optimization is a lively field of applied mathematics in whichtechniques from combinatorics, linear programming, and the theory ofalgorithms are used to solve optimization problems over discrete structures, suchas networks or graphs. The course will emphasize algorithmic solutions togeneral problems, their complexity, and their application to real-world problemsdrawn from such areas as VLSI design, telecommunications, airline crewscheduling, and product distribution. Topics will be selected from: Networkflow, optimal matching, integrality of polyhedra, matroids, andNP-completeness.Recommended background: At least one course in graph theory, combinatoricsor optimization (e.g., MA 2271, MA 2273 or MA 3231).This course will be offered in 2020-21, and in alternating years thereafter.