APM6664

Combinatorial Optimization

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. Student must meet prerequisite (APM 5663) or have instructor permission.  Formerly APM 664.

APM664

College of Arts and Sciences