APM 6664 - 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 minimal-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.

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

Course revisions made after the Graduate Catalog publication date will be posted in the Graduate Catalog Addendum.