CS60023 Approximation and Online Algorithms

Instructor:

 Swagato Sanyal

Teaching Assistant:

 Arshdeep Singh

Course overview:

 This course is divided into the following two parts:
  1. Designing and analyzing polynomial time algorithms that approxiately solve NP-hard optimization problems,

  2. Designing and analyzing algorithms in the online computational model in which the input arrives piece by piece, and an irrevocable decision needs to be made whenever such a bit arrives without the knowledge about future bits.
  The course is of theoretical flavour and involves mathematically deriving bounds on performance of algorithms or establishing non-existence of algorithms. Have a look at the webpage of the last offering of this course to get a sense of the topics to be covered.

Pre–requisites:
  1. Mathematical maturity.

  2. Algorithms-II and Discrete Structures for UG students.

Classes:

 Venue: Microsoft Teams. Timings: Monday 5-6pm, Thurday 5-6pm, Friday 5-6pm.

Evaluation:

 2-3 long/short tests (approximately evenly spaced in the semester), 3-4 assignments, presentations, attendance+other class acitivities (teacher's assessment).

References:
  1. V. Vazirani, Approximation Algorithms, Springer, 2003.

  2. D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge, 2011.

  3. A. Fiat and G. Woeginger, Online Algorithms, Lecture Notes in Computer Science, no. 1442, Springer, 1998 (Edited Volume).
Lectures:

Lectures Date Class notes Reference Reading
1. Course introduction and logistics 04/01/21 -- --
2. NP-optimization problems and approximation algorithms 07/01/21 Click here Vazirani Appendix A.3
3. Vertex-cover: 2-approximation algorithm based on maximal matching 08/01/21 Click here Vazirani Chapter 1
4. Set-cover: greedy H_n-approximation algorithm 11/01/21 -- Vazirani Chapter 2
5. Weighted vertex cover: 2-approximation algorithm based on layering 14/01/21 Click here Vazirani Chapter 2
6,7&8. Steiner tree and TSP 15/01/21,
18/01/21 		Click here Vazirani Chapter 3
9&10. Linear programming, duality, rounding algorithms for weighted vertex cover and set cover 28/01/21,
29/01/21 		Click here Vazirani Chapters 12 and 14
11. Randomized rounding algorithm for set-cover 01/02/21 Click here Vazirani Chapter 14
12. Dual-fitting applied to Set-cover greedy 04/02/21 Click here Vazirani Chapter 13
13. Dual-fitting applied to constraint set multicover 05/02/21 Click here Vazirani Chapter 13
14. FPTAS for Knapsack 08/02/21 Click here Vazirani Chapter 8
15. FPTAS, pseudopolynomial time exact algorithms and strongly NP-hard problems. Bin-packing. First-Fit algorithm. 11/02/21 Click here Vazirani Chapters 8 and 9
16. Bin-packing. Asymptotic PTAS. 12/02/21 Click here Vazirani Chapter 9
17. Makespan minimization. Greedy 2-approximation. Least processing Time First. 15/02/21 Click here Vazirani Chapter 10, Kleinberg-tardos Chapter 11
18. Least processing Time First: optimal analysis. 18/02/21 Click here Lecture notes from Ola Svensson's course
19. Makespan minimization: PTAS. 19/02/21 Click here Vazirani Chapter 9
20. Online algorithms: Introduction 22/02/21 Click here Fiat-Woeginger Chapter 3
21. Deterministic online paging algorithms. 25/02/21 Click here
22&23. Resource augmentation. Randomized paging algorithm: MARK. 26/02/21 and 04/03/2021 Click here
24. Randomized lower bound on competitive ratio for paging 08/03/21 Click here Fiat-Woeginger Chapter 4
25. Online steiner tree 11/03/21 Click here Tim Roughgarden's lecture notes.
26. Online bipartite matching 12/03/21 Click here http://www.cs.cornell.edu/courses/cs6820/2012fa/handouts/djk.pdf
27-29. Online bipartite matching-RANKING algorithm 15/03/21-19/03/21 Click here
30. Uncapacitated facilities location (guest lecture by Prof. Sudebkumar Prasant Pal) 22/03/21 Slides Williamson-Shmoys, Vazirani
31-32. Complementary slackness and primal-dual schema 25/03/21-26/03/21 Click here Vazirani Chapter 15