Times Mo/We 9:30AM - 10:45AM
Location 200-305
Instructor Amin Saberi (saberi at stanford) Office Hours By appointment
Course Assistants Farnaz Ronaghi (farnaaz at stanford) Wed. 5-7pm at Huanag 203

Special location on Feb 1st & Mar 7th: Huang B007

Recommended Texts

Class Discription

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 Load and Grading

Homework: 4 homework assignments of 10% each.
Midterm: in class, close-book, and 30%
Final: 35%.
(if you get more than 100, you will get an A+ in this class).

Tentative Outline

  1. Motivation for the course: (1 week)
    • several examples
    • lp vs ip
    • np-hardness
    • approximation algorithms
  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)