PG elective, 3 credits, LTP 3-0-0
Spring 2020: Lectures Mondays, Thursdays and Fridays, 5 pm - 6 pm, Room 108 CSE. First lecture January 02, 2020, thursday.
Instructor: Sudebkumar Prasant Pal
Student enrollment key in cse moodle for CS60023 AOA Approximation and Online Algorithms (Spring 2020) is AOASTU
ERP registration for 3rd year cse UG students may be enabled January 01, 2020.
Teaching assistant: Mahendra Singh Kanyal
Student Enroll code for moodle: AOASTU
CSE Moodle:
Registrants Spring 2020:
===========================
1 15CS30013 Dhiraj Kumar Tandi
2 16CS10004 Aitipamula Aravind
3 16CS10020 Gaurav Kumar Jha
4 16CS10021 Gavali Harshad Abhiman
5 16CS10061 G Vishal
6 16CS30003 Aman Kumar
7 16CS30007 Ayush Mahajan
8 16CS30025 Paritosh Sinha
9 17CS10033 Pittu Madhusudhan Reddy
10 17CS10039 Prashant Shishodia
11 17CS30008 Arnab Maiti
12 17CS30030 Sanket Rajendra Meshram
13 17CS30042 Amatya Sharma
-----------------------------------------
Objectives of the course
=====================
It is well-known that most combinatorial and geometric optimization problems arising out of real- world scenarios turn out to be NP-hard. From computational complexity theory, we know that it is impossible to design efficient algorithms for solving such problems exactly unless P=NP, which is very unlikely to be the case. This does not obviate the need for designing efficient polynomial time algorithms for these problems. However, we may relax the stringent requirement of computing an exact optimal solution. In practice, it serves our purpose well enough if we can obtain a near- optimal solution instead of an exact optimal, especially when the former can be computed much faster. This results in the notion of the ‘approximate’ solution of an optimization problem. As a computer scientist and engineer, it is often worthwhile to focus on designing efficient algorithms that output an approximate solution, but at the same time provide a relative performance guarantee that the value of the solution is within some factor (this factor is called the ‘approximation ratio’) of the optimal value.
In the same spirit of approximation ratios, an online algorithm’s performance is measured in terms of competitive ratios. Many algorithmic problems that arise in practice are of online nature. In these problems, the input is only partially available because some relevant input arrives only in the future and is not accessible at present. An online algorithm must generate output without the knowledge of the entire input.
======================================
Part I: Approximation algorithms
[27 hours]
1. Introduction and performance measures [1 hour]
2. Greedy Algorithms and Local Search: [13 hours] (a) Unweighted Vertex Cover Problem (1 hour), (b) Minumum-Degree Spanning Tree (1 hour), (c) The Traveling-salesman Problem (1 hour), (d) The k-Center Problem (1 hour), (e) Multiway Cut and K-Cut Problems (1 hour), (f) Scheduling Jobs with Deadlines on a Single Machine (1 hour), (g) Scheduling Jobs on Identical Parallel Machines (1 hour) (h) The Set Cover Problem (1 hour), (i) Shortest Superstring (1 hour), (j) The Knapsack Problem (1 hour), (k) The Bin-packing Problem (1 hour), (l) Art Gallery Problems (2 hours)
3. Rounding Data and Dynamic Programming: [4 hours] Approximation Schemes for (a) The Knapsack Problem (1 hours) (b) Scheduling Jobs on Identical Parallel Machines (2 hours), (c) The Bin-packing problem (1 hours)
4. Deterministic Rounding of Linear Programs: [5 hours] (a) A Single-machine Scheduling Problem (1 hour), (b) The Uncapacitated Facility Location Problem (2 hours) and (c) The Bin-packing Problem (2 hours).
5. The Primal-dual Method: [4 hours] (a) The Set Cover Problem (1 hour), (b) The Feedback Vertex Set problem (2 hours), (c) Weighted Vertex Cover Problem (1 hours)
Part II: Online algorithms
[13 hours]
1. Competitive analysis of online algorithms [1 hour]
2. The Paging Problem [1 hour]
3. Amortized analysis of online algorithms [1+1/2 hour]
4. The List Update Problem [1 hour]
5. Problem of searching for a target in a bounded or unbounded region. [2+1/2 hours]
6. Online graph coloring [2 hours]
7. Online machine learning problems [2 hours]
8. Online scheduling algorithms [2 hours]
Total 40 hours
Textbooks
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).
Reference texts
1. M. R. Garey and D. S. Johnson, Computers and Intractibility: A guide to the theory of NP- completeness, W. H. Freeman, 1979.
2. R. Motwani, Lecture Notes on Approximation Algorithms, Volume 1, No. STAN-CS-92-1435, Stanford University, 1992
3. S. K. Ghosh, Approximation algorithms for art gallery problems in polygons and terrains, (Survey Paper), Lecture Notes in Computer Science, No. 5942, pp. 21-34, Springer, 2010.
4. S. Albers, Competitive Online Algorithms, Lecture notes, Max Plank Institute, Saarbrucken, 1996.
5. S. K. Ghosh and R. Klein, Online algorithms for searching and exploration in the plane, (Survey Paper), Computer Science Review, vol. 4, pp. 189-201, 2010.
==================================================================================================
Registrants Spring 2019 for CS60023: Satyam Sevenya, Thota Vineeth Kumar, Tushar Sinha, Lingam Vishal Reddy, Patil Shubham Anil, Soham Mukherjee and Mahendra Singh Kayal =================================================================================================
Registrants Autumn 2018 for CS60023: Malaviya Rakesh, Samboji Krishna Maithreya, Aditya Anand, Apoorva Kumar, Nitish Kumar Rai, Ray Saurav Prabhakar, Vedic Partap, Sahare Prashik Siddharth, Vivek Gupta
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Registrants Autumn 2017 for CS60023: Jeenu Grover, Koushik, Kunal, Abhay, Shubham Singh, Shubham Parekh, Shreyans, Ritabrata, Aditya Jain, Shashank, Ayush, Mayank, Gulab, Aswanth, Shirgure, Madhuresh and Vishnu
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++