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 k-Cut 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) k-Centre 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. Semi-definite Programming: the Maximum Cut Problem. [Problem Set 2 due.]
  • Wednesday October 18th. Semi-definite 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; Multi-Commodity 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: 2-connectivity. [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: k-connectivity.

    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.