CS 695
Fall 2010
Special Topics on Theoretical Computer Science
Approximation Algorithms
The area of approximation algorithms is aimed at giving provable guarantees on the performance of algorithms for hard problems. In this course, we will learn approximation algorithms and their analysis. We will also discuss about online algorithms and competitive analysis.
CS 583 or equivalent, or permission of the instructor. Please contact with the instructor if you are not sure.
Approximation Algorithms, by Vijay V. Vazirani, Springer, 2003
Introduction to Algorithms, by Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, The MIT Press, 3rd Edition 2009
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995
Lectures | Dates | Topics | Lecture Notes | Scopes | Notes |
1 | August 31 | Introduction | |||
2 | September 7 | ||||
3 | September 14 | ||||
4 | September 21 | ||||
5 | September 28 | ||||
6 | October 5 | ||||
7 | October 12 | ||||
8 | October 19 | ||||
9 | October 26 | ||||
10 | November 2 | ||||
11 | November 9 | ||||
12 | November 16 | ||||
Thanksgiving
recess
No class |
November 23 | ||||
13 | December 7 | ||||
14 | December 14 | Project presentations |
A. Fiat, R.M. Karp, M. Luby, L.A. McGeoch, D. Sleator, and N. Young, ``Competitive Paging Algorithms'', Journal of Algorithms, Volume 12, Number 4, pages 685-699, 1991.
N. Reingold, J. Westbrook, D. Sleator, ``Randomized Competitive Algorithms for the List Update Problem'', Algorithmica, Volume 11, Number 1, pages 15-32, 1994.
B. Awerbuch, F. T. Leighton, ``A simple local-control approximation algorithm for multicommodity flow'', Proceedings of the 34th IEEE Annual Foundations of Computer Science (FOCS), pages 459-468, 1993.
D. D. Sleator and R. E. Tarjan, ``Amortized efficiency of list update and paging rules'', Communications of the ACM (CACM), Volume 28 , Issue 2, pages 202-208, 1985.
D. D. Sleator and R. E. Tarjan, ``Self-adjusting binary search trees'', Journal of the ACM (JACM), Volume 32, Issue 3, pages 652-686, 1985.
Avrim Blum, ``On-Line Algorithms in Machine Learning'', Online Algorithms: The State of the Art, Lecture Notes In Computer Science, Volume 1442, pages 306-325, 1998.
S. Arora, ``Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems'', Journal of the ACM (JACM), Volume 45, Issue 5, pages 753-783, 1998.
D. S. Hochbaum, ``Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems'', pages 94-143, in Approximation Algorithms for NP-hard Problems, 1997.
N. Bansal, N. Buchbinder, and J. Naor, ``A Primal-dual randomized algorithm for weighted paging'', Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 507-517, 2007.
L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein, ``Scheduling to Minimize Average Completion Time: Off-line and Online Approximation Algorithms'', Mathematics of Operations Research, Volume 22, Number. 3, pages 513-544, 1997.
J. Hastad, ``Some Optimal Inapproximability Results'', Journal of the ACM (JACM), Volume 48, Issue 4, pages 798-859, 2001.
C. Phillips, C. Stein, E, Torng and J. Wein, ``Optimal Time-Critical Scheduling via Resource Augmentation'', Algorithmica, Volume 32, Number 2, pages 163-200, March 2008.
Muthukrishnan, ``Data streams: algorithms and applications'', Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 413-413, 2003.
P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, ``Approximating Extent Measures of Points'', Journal of the ACM (JACM), Volume 51, Number 4, pages 606-635, 2004.
Y. Azar and N. Levy, ``Multiplexing packets with arbitrary deadlines in bounded buffers'', Lecture notes in Compute Science, Proceedings of Scandinavian Workshop on Algorithm Theory (SWAT), pages 5-16, 2006.
R. L. Graham, ``Bounds on Multiprocessing Time Anomalies'', SIAM Journal of Applied Mathematics, pages 416-429, 1969.
M. R. Garey and R. L. Graham, ``Bounds for Multiprocessor Scheduling with Resource Constraints'', SIAM Journal of Computing, pages 187-200, 1975.
D. Karger, C. Stein, and J. Wein, `` Scheduling Algorithms'', a chapter written for the CRC Handbook on Algorithms, 1997.
Tentative Grading:
Assignments (20%)
Two presentations (40%)
A project. You can work on designing and analyzing an approximation algorithm for a NP-hard problem, or designing and analyzing an online algorithm for an online problem, or implementing some known approximation algorithms for some specific applications and provide experimental analysis. (40%)
Academic Honesty:
Disability Statement: