APPROXIMATION ALGORITHMS


Schedule.
Week 1.
Monday September 4th. Holiday: No Lecture.
Wednesday September 6th. Introduction: the Travelling Salesman Problem; the Vertex Cover Problem; the Maximum Clique Problem.
Week 2.
Monday September 11th. Cut Problems: the Multiway Cut Problem; the Minimum kCut Problem.
Wednesday September 13th. Randomised Algorithms: the Set Cover Problem; the Hitting Set Problem.
Week 3.
Monday September 18th. Randomised Algorithms: the Maximum Satisfiability Problem.
Wednesday September 20th. Randomised Algorithms: the Minimum Congestion Flow Problem. [Problem Set 1 assigned.]
Week 4.
Monday September 25th. Bioinformatics: the Shortest Superstring Problem.
Wednesday September 27th. Facility Location: the (Asymmetric) kCentre Problem.
Week 5.
Monday October 2nd. Polynomial Time Approximation Schemes: the Knapsack Packing. [Problem Set 1 due.]
Wednesday October 4th. Polynomial Time Approximation Schemes: Bin Packing. [Problem Set 2 assigned.]
Week 6.
Monday October 9th. Holiday: Thanksgiving.
Tuesday October 10th. Network Optimisation: the Unsplittable Flow Problem.
Wednesday October 11th. Network Optimisation: the Confluent Flow Problem.
Week 7.
Monday October 16th. Semidefinite Programming: the Maximum Cut Problem. [Problem Set 2 due.]
Wednesday October 18th. Semidefinite Programming: Graph Colouring. [Problem Set 3 assigned.]
Week 8.
Monday October 23rd. Linear Programming Duality: the Set Cover Problem.
Wednesday October 25th. The Primal Dual Method for Linear Programming and Approximation Algorithms.
Week 9.
Monday October 30th. The Primal Dual Method: the Set Cover Problem; MultiCommodity Flows.[Problem Set 3 due.]
Wednesday November 1st. The Primal Dual Method: The Steiner Forest Problem. [Problem Set 4 assigned.]
Week 10.
Monday November 6th. The Primal Dual Method: the Facility Location Problem.
Wednesday November 8th. Polynomial Time Approximation Schemes: Euclidean Travelling Salesman Problem.
Week 11.
Monday November 13th. Graph Connectivity: 2connectivity. [Problem Set 4 due.]
Wednesday November 15th. More Graph Connectivity. [Problem Set 5 assigned.]
Week 12.
Monday November 20th. Iterative Rounding: the Survivable Network Design Problem.
Wednesday November 22nd. Graph Connectivity: kconnectivity.
Week 13.
Monday November 27th. The Multicut Problem.
Wednesday November 29th. The Sparsest Cut.
Week 14.
Monday December 4th. The Last Lecture. [Problem Set 5 due.]
Friday December 8th. Final Exam 10am.