_ 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
Algorithm Design by
Kleinberg and Tardos, 2005
Mathematics by Lovasz, Pelikan and Vesztergombi, 2003
Optimization, by Cook, Cunningham, Pulleyblank
and Schrijver, 1997
mathematical programming (integer and non-linear) techniques for optimization.
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.
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.
dates: Jan 19-31, Jan 31-Feb 14, Feb 14-Feb 28, Feb 28-Mar 14.
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 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
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 3, chapter 4 of BVR
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
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
Homework 1 (due Jan 31st). Solution.
Homework 2 (due Feb 14st). Solution.
Homework 3 (due Feb 28th). Solution.
Homework 4 (due Mar 14th). Solution.
_ 2016 midterm and solutions.
midterms: I and II
- Motivation for the course: (1
Basic graph theory (3 weeks)
- several examples
- LP vs IP
- approximation algorithms
Running time, Asymptotics
Refresh LP and duality -- simplex
Shortest path, matching, flow,
min-cost flow, several applications (4 weeks)
NP-completeness (2 weeks)
Approximation algorithms (4 weeks)
- Graphs, Trees, Cayley's Theorem
- Depth First Search, Breadth First
- Minimum Spanning Trees
- Eulerian graphs, Hamiltonian