This is the home page for a course of 24 lectures to Cambridge MMath/MASt
(Part III) students.
It will be given M, W, F at 11am in MR14, starting October 9, 2015, and ending December 2.
Here are course notes. I aim to make each lecture a self-contained unit on a topic, with notes of typically four A4 pages. If you think you find a mistake in the notes, check that you have the most recent copy (in case a correction has already been made). Otherwise, please let me know and I will make the correction.
After each lecture I will be writing a few comments in the course blog: to emphasize an idea, answer an interesting question (which perhaps a student sends to me in email or asks in lecture).
There will be 3 examples sheets and classes for these, in which I will discuss their solutions.
Tuesday November 3: 16:00-18:00 MR14
Tuesday December 1: 16:00-18:00 MR14
Tuesday January 19: 16:00-18:00 MR14
The course finishes 2 December 2015.
Past exam questions
Recommended books and notes
You can find these books in libraries around Cambridge. Clicking on the title link will show you where the book can be found.
1. M.S. Bazaraa, J.J. Jarvis and H.D. Sherali: Linear Programming and Network Flows, Wiley (1988).
2. D. Bertsimas, J.N. Tsitsiklis: Introduction to Linear Optimization. Athena Scientific (1997).
3. N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory. Cambridge University Press (2007).
4. M. Osborne, A. Rubinstein: A Course in Game Theory. MIT Press (1994).
Other resources and further reading
5. S. Arora, B. Barak: Computational Complexity - A Modern Approach. Cambridge University Press (2009).
6. S. Boyd and L. Vandenberghe: Convex Optimization. Cambridge University Press (2004).
7. H. Moulin: Axioms of Cooperative Decision Making. Cambridge University Press (1988).
8. A. D. Taylor: Social Choice and the Mathematics of Manipulation. Cambridge University Press (2005).
• Lagrangian sufficiency theorem. Lagrange duality. Supporting hyperplane theorem. Sufficient conditions for convexity of the optimal value function. Fundamentals of linear programming. Linear program duality. Shadow prices. Complementary slackness. 
• Simplex algorithm. Two-phase method. Dual simplex algorithm. Gomory’s cutting plane method. 
• Complexity of algorithms. NP-completeness. Exponential complexity of the simplex algorithm. Polynomial time algorithms for linear programming. 
• Network simplex algorithm. Transportation and assignment problems, Ford-Fulkerson algorithm, max-flow/min-cut theorem. Shortest paths, Bellman-Ford algorithm, Dijkstra’s algorithm. Minimum spanning trees, Prim’s algorithm. MAX CUT, semidefinite programming, interior point methods. 
• Branch and bound. Dakin’s method. Exact, approximate, and heuristic methods for the travelling salesman problem. 
• Cooperative and non-cooperative games. Two-player zero-sum
games. Existence and computation of Nash equilibria in non-zero sum
games, Lemke-Howson algorithm. Bargaining. Coalitional games, core,
nucleolus, Shapley value. Arrow's theorem, Gibbard-Satterthwaite
theorem. Mechanism design. Vickrey-Clarke-Groves
mechanisms. Auctions, revenue equivalence, optimal auctions.