MS&E 212  Combinatorial Optimization
Course description
Combinatorial and mathematical programming (integer and nonlinear) 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; NPcompleteness.
Applications: topics will be illustrated with applications from operations management, bioinformatics, computer systems, and electronic commerce.
Course information
MS&E 212  Combinatorial Optimization  Winter 2019
Instructor: Amin Saberi
Huang Engineering Center, Rm 309
Office Hours: Thursday 1:30  2:30 pm
saberi at stanford dot edu
Course Assistant: Nolan Skochdopole
Pizza Website
Textbook
Recommended Books:
Algorithm Design by Kleinberg and Tardos, 2005
Discrete Mathematics by Lovasz, Pelikan and Vesztergombi
Course Load and Grading
Homework: 4 assignments of 10% each.
Midterm: in class, 30%. Tuesday Feb. 12 Practice Midterm.
Final: 35% (if you get more than 100, you will get an A+). Tuesday Mar. 19 3:306:30 pm, Location: Littlefield 107 (normal class room) Practice final.
Tentative Schedule
Basic concepts and definitions
Cayley's theorem, Prufer codes
Minimum spanning trees, applications in phylogeny
Eulerian and Hamiltonian cycles, DNA sequencing
Introduction to algorithms
Matchings, flows, linear programs and LPduality
Intractability and NPhardness
Advanced techniques
Randomization
Probabilistic method, random graphs
Random walks on graphs, hitting and cover times
Matching via matrix inversion
Approximation algorithms
Vertex cover and set cover
Traveling salesman problems
Maximum cuts and semidefinite relaxations
