MS&E 112: Mathematical Programming and Combinatorial Optimization (MS&E 212)
Combinatorial and mathematical programming (integer and non-linear) techniques for optimization. Topics: linear program duality and LP solvers; integer programming; combinatorial optimization problems on networks including minimum spanning trees, shortest paths, and network flows; matching and assignment problems; dynamic programming; linear approximations to convex programs; NP-completeness. Hands-on exercises. Prerequisites: 111 or
MATH 103,
CS 106A or X.
Last offered: Winter 2017
MS&E 319: Approximation Algorithms
Combinatorial and mathematical programming techniques to derive approximation algorithms for NP-hard optimization problems. Prossible topics include: greedy algorithms for vertex/set cover; rounding LP relaxations of integer programs; primal-dual algorithms; semidefinite relaxations. May be repeated for credit. Prerequisites: 112 or
CS 161.
Last offered: Autumn 2016
| Repeatable
for credit
Filter Results: