Course Information

 

_      Times: Tue/Thu 3:00PM - 4:20PM

_      Location: Building 380, 380X

_       Instructor: Amin Saberi (saberi at stanford), Office hours: Thursday 4:30-6:00 pm

Recommended Texts

_      Algorithm Design by Kleinberg and Tardos, 2005

_      Discrete Mathematics by Lovasz, Pelikan and Vesztergombi, 2003      

_      Combinatorial Optimization, by Cook, Cunningham, Pulleyblank and Schrijver, 1997

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, bioinformatics, computer systems, and electronic commerce.

Course Load and Grading

 

_      Homework: 4 homework assignments of 10% each. 

_      Homework dates: Jan 19-31, Jan 31-Feb 14, Feb 14-Feb 28, Feb 28-Mar 14.

_      Midterm: in class and closed book on Feb 14, and 30% of the grade.

_      Final: 35%. (if you get more than 100, you will get an A+ in this class). 

Lecture notes

 

_      Lecture 1: Basic Graph Theory Concepts, Trees, Cayley's Theorem. See the notes as well as Graph Theory slides

_      Lecture 2: Eulerian Circuits and DNA sequencing. See the notes. Also check out DNA Arrays for more information.

_      Lecture 3: Minimum Spanning Trees. See the notes. 

_      Lecture 4: Network flows, maximum-flow minimum-cut theorem. See the notes as well as the additional material on the Ford-Fulkerson algorithms

_      Lectures 5 & 6: Applications of networks flows. See the notes as well as the additional material on KargerÕs algorithm for finding global minimum cut.

_      Lecture 7: Linear programs  (A quick review).  See also chapter 3chapter 4 of BVR 

_      Lecture 8: Minimum cost flows. See also chapter 5 of BVR.

_      Lectures 9 & 10: Approximation algorithms I. See also the additional material on NP-Completeness.

_      Lecture 11: The stable marriage problem. See also this on practical applications.

_      Lectures 12 & 13: Approximation algorithms II. See also chapter 26 of VaziraniÕs book on maximum cut and semidefinite programming.

_      Lecture 13 & 14: SpernerÕs lemma and applications: BrouwerÕs fixed point theorem, fair allocation, and rental harmony. See SuÕs excellent exposition. You can also look at this note with a more mathematical treatment for your information.   

_      Lecture 15: mechanism design and sponsored auctions. See these slides.

 

 

Homeworks

 

_      Homework 1 (due Jan 31st). Solution.

_      Homework 2 (due Feb 14st). Solution.

_      Homework 3 (due Feb 28th). Solution.

_      Homework 4 (due Mar 14th). Solution.

 

 

 

Sample midterm

_       2016 midterm and solutions.

_       Practice midterms: and II

 

Sample final

_       2016 finals

 

Tentative Outline

  1. Motivation for the course: (1 week)
  2. Basic graph theory (3 weeks)
  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)