Academics

  /  

Courses

  /  

Descriptions

  /  

Keep

IEMS 452: Combinatorial Optimization

VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

Linear programming (simplex, duality), Network flows (shortest path, max flow, min cut); These are “soft” prerequisites, i.e., even without this background it should be easy to follow the material.

Description

List of topics:

1. Matchings
   1. Basic results and related concepts
   2. Algorithm for cardinality bipartite matching
2. Weighted matchings
   1. Review of polyhedral theory
   2. The algorithm
   3. Polyhedral analysis
3. Matroids
   1. Basic definition
   2. The matroid intersection algorithm

MATERIALS:

W. Cook, W. Cunningham, W. Pulleyblank, and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, 1998, ISBN 0-471-55894-X.