Topics in Optimization (ENGN 2912P)

Home   Assignments   Lectures  
Lecture: MWF 11am-11:50am in Barus & Holley 159

Pedro Felzenszwalb
Email: pff (at)
Office: Barus & Holley 355
Office hours: Monday 2-4pm in BH355

Jeroen Chua
Email: jeroen_chua (at)
Office hours: Thursday 2-4pm in BH317

Course description
This course will cover various topics in discrete and continuous optimization. Topics include graph algorithms, dynamic programming, linear programming, convex optimization and coarse-to-fine methods.

Combinatorial Optimization. Schrijver. Springer.
Introduction to Algorithms. Cormen, Leiserson, Rivest, Stein. MIT Press.
The Design and Analysis of Computer Algorithms. Aho, Hopcroft, Ullman. Addison-Wesley.
Algorithm Design. Kleinberg, Tardos. Addison-Wesley.
Randomized Algorithms. Motwani and Raghavan.

Preliminary list of topics for 2015

Shortest paths
- Dijkstra, Bellman-Ford, Floyd-Warshall
- Min-plus matrix multiplication
- Minimum-ratio paths
- String edit and time warping

- Max-flow / Min-cut
- Min-cost circulation
- Bipartite matching

Linear programming
- Simplex
- Duality

Dynamic programming
- Sequence labeling
- Graph labeling
- Piecewise quadratic fitting

Approximation algorithms
- Min-cover (greedy)
- Max-cut (local search)
- Packing (rounding + DP)
- LP relaxations

Other topics
- Randomized Algorithm
- Branch-and-bound
- Heuristic search
- Local search
- Convex optimization