Combinatorial Optimization >> Content Detail

Calendar / Schedule


1Course Introduction

Matching Theory
2The Hungarian Algorithm
3Edmonds' Algorithm
4Polyhedral Combinatorics
5The Matching Polytope I
6The Matching Polytope II
7Flow Theory and Duality
8Max-flow AlgorithmsAssignment 1 due
9Min-cut Algorithms
10Min-cost Flow
11Strongly Polynomial Algorithms
12Linear Programming Duality
13The Simplex AlgorithmAssignment 2 due
14Exam I
15The Simplex Algorithm (contd.)
16Complementary Slackness

Primal-dual Algorithm
17The Ellipsoid Algorithm I: Ideas
18The Ellipsoid Algorithm II: Details
19Separation Oracles I: Convex Problems
20Oracles II: Combinatorial Problems
21NP-completenessAssignment 3 due
22, 23Approximation Algorithms
24The Relax-and-round Paradigm
25Exam IIAssignment 4 due
26, 27Projects Reviews


© 2009-2020, All Rights Reserved.
Higher Ed Space ® is a registered trademark of AmeriCareers LLC.