Instructor
Pedro Felzenszwalb
Email: pff (at) brown.edu
Office: Barus & Holley 355
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.
References
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.
Preliminary list of topics for 2014
Shortest paths
- Dijkstra, Bellman-Ford, Floyd-Warshall
- Min-plus matrix multiplication
- Minimum-ratio paths
- String edit and time warping
Matroids
- Spanning trees and other applications
- Greedy algorithm
- Matroid intersection
Flow
- 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 relaxation
Other topics
- Branch-and-bound
- Heuristic search
- Local search
- Convex optimization