|Times||Mo/We 9:30AM - 10:45AM|
|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
- Algorithm Design by Kleinberg and Tardos, 2005
- Discrete Mathematics by Lovasz, Pelikan and Vesztergombi [LPV] (available here for Stanford IPs)
- Combinatorial Optimization, by Korte and Vygen, Theory and Algorithms, 2002
- Combinatorial Optimization, by Cook, Cunningham, Pulleyblank and Schrijver, 1997
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 GradingHomework: 4 homework assignments of 10% each.
Midterm: in class, close-book, and 30%
(if you get more than 100, you will get an A+ in this class).
- Motivation for the course: (1 week)
- several examples
- lp vs ip
- approximation algorithms
- Graphs, Trees, Cayley's Theorem
- Depth First Search, Breadth First Search
- Minimum Spanning Trees
- Eulerian graphs, Hamiltonian graphs