APM 664 - Combinatorial Optimization

(4 credits)

Duality and Farkas’ Lemma. Efficient algorithms, optimality conditions and polyhedral structures of problems in discrete optimization including optimal trees, optimal matchings and minimum-cost flow. Additional topics to include theory, approximation algorithms, matroid optimization and cutting planes algorithm for studying problems such as the traveling salesman and stable set problems.

Prerequisite(s): Student must meet prerequisite (APM 563) or have instructor permission.