PG elective, 3 credits, LTP 3-0-0
Autumn 2017: Lectures Wednesday 10 am, Thursdays 9 am and Fridays 11 am
Instructors: Sudebkumar Prasant Pal and Subir Kumar Ghosh
Teaching assistant: Pritam Bhattacharya
Objective
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 Jeenu Grover, Koushik, Kunal, Abhay, Shubham Singh, Shubham Parekh, Shreyans, Ritabrata, Aditya Jain, Shashank, Ayush, Mayank, Gulab, Aswanth, Shirgure, Madhuresh and Vishnu