MS&E 212 - Combinatorial Optimization

Course description

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.

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

  • Location: Littlefield 107

  • Times: Tuesdays and Thursdays 3:00 pm - 4:20 pm

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

  • naskoch at stanford dot edu

  • Office Hours: Wednesday 2:00 pm - 4:00 pm (basement of Huang)

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

  • Final: 35% (if you get more than 100, you will get an A+).

Tentative Schedule

  1. Basic concepts and definitions

    1. Cayley's theorem, Prufer codes

    2. Minimum spanning trees, applications in phylogeny

    3. Eulerian and Hamiltonian cycles, DNA sequencing

  2. Introduction to algorithms

    1. Matchings, flows, linear programs and LP-duality

    2. Intractability and NP-hardness

  3. Advanced techniques

    1. Randomization

      1. Probabilistic method, random graphs

      2. Random walks on graphs, hitting and cover times

      3. Matching via matrix inversion

    2. Approximation algorithms

      1. Vertex cover and set cover

      2. Traveling salesman problems

      3. Maximum cuts and semi-definite relaxations