Approximation algorithms – Lectures

Posted on September 5, 2013 by benkoczi| Leave a comment
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.

Comments are closed.