Times MW 9:30am - 10:45pm
Location McCullough 122 
Instructor Amin Saberi (saberi at stanford dot edu) Office Hours TBD
or by appointment
Course Assistant Adam Guetz (guetz at stanford dot edu) Office Hours F 9:30-10:45
McCullough 122

 Texts


  Recommended Books:

  Discrete Mathematics by Lovasz, Pelikan and Vesztergombi  (available here for Stanford IPs)
  Combinatorial Optimization, by Korte and Vygen, Theory and Algorithms, 2002

  Cook, Cunningham, Pulleyblank and Schrijver,Combinatorial Optimization, 1997
  Hillier and Lieberman, Introduction to Operations Research, 8th edition, 2005


Class 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, network design, and electronic commerce.

Course Load and Grading

Homework: 4 homework assignments of 10% each.

Midterm: in class and 30%

   Final or Project: a group project (2-3 students in each group) worth 35%.

    (if you get more than 100, you will get an A+ in this class).

Tentative Outline

  1. Motivation for the course: several examples; lp vs ip, np-hardness,
    approximation algorithms (1 week)
  2. Basic graph theory (3 weeks)
       Graphs, Trees, Cayley's Theorem
       Depth First Search, Breadth First Search
       Minimum Spanning Trees
       Eulerian graphs, Hamiltonian graphs 
  3. Running time, Asymptotics  (1 week) 
  4. Refresh LP and duality -- simplex (1 week)
  5. Shortest path, matching, flow, min-cost flow, several applications (4 weeks)  
  6. NP-completeness (2  weeks)
  7. Approximation algorithms (4 weeks)