Approximation algorithms – Lectures
- Sep 5 – 19
- Read Chapter 1 – Introduction and Appendix A – Linear programing.
- Sep 19 – 26
- Read Chapter 2 (greedy and local search): The k-center + scheduling with deadlines on a single machine + scheduling on parallel identical machines.
- Oct 1-3
- Chapter 2: TSP + Max float
- Oct 8-10
- Chapter 2: edge colouring, Chapter 3 (rounding data and PTAS): a PTAS for the knapsack problem
- Oct 15-17
- Chapter 3: PTAS for scheduling on identical parallel machines
- Oct 22-24
- Chapter 3: scheduling on identical parallel machines, bin packing
- Oct 29-Nov 14
- Chapter 4 (deterministic rounding): sections 4.1 – 4.5 (job scheduling to minimize weighted sum of completion times, the ellipsoid algorithm, prize collecting Steiner tree and UFL)
- Nov 19-28
- Student presentations (shortest super-string, Canadian traveller in double valued graphs, PTAS for max-colouring in trees, minimum knapsack greedy and primal-dual (Section 7.5), asymmetric TSP, and partial set cover).
- Dec 3-5
- Chapter 7 (primal-dual): 7.2, 7.6 (feedback vertex set, UFL)
This entry was posted in approx-course
. Bookmark the permalink