CS 795
Fall 2008
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.
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 McGraw-Hill Companies, 2nd Edition 2001
Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995
Lectures | Dates | Topics | Lecture Notes | Scopes | Notes |
1 | August 28 | Introduction | Distributed in class | Chapters 1, 12, CLSR 35 | |
2 | September 4 | Set cover | Distributed in class | Chapters 2, 14 | |
3 | September 11 | Set cover, duality | Distributed in class | Chapters 12, 13, 15 | |
4 | September 18 | Knapsack, Bin packing | Distributed in class | Chapters 8, 9 | |
5 | September 25 | Randomized algorithms | Distributed in class | Chapter 14, CLSR 35 | |
6 | October 2 | Randomness, MAX SAT | Distributed in class | Chapters 16, 28 | |
7 | October 9 | Machine scheduling | Distributed in class | Chapters 5, 24 | IPL paper |
8 | October 16 | Semi-definite programming | Distributed in class | Chapters 10, 17 | |
9 | October 23 | NP-hard scheduling problems | Distributed in class | Papers | Survey talk |
10 | October 30 | Real-time scheduling | Power management algorithms | ||
11 | November 6 | Venkat, Yogesh | buffer management; scheduling | Paper presentation | |
12 | November 13 | Vinay, Raheem | scheduling, geometric algorithm | Paper presentation | |
13 | November 20 | TBD | Project presentations | ||
November 27 | No class. Thanksgiving. | ||||
14 | December 4 | TBD | Project presentations |
1. 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
2. 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
3. N. Bansal, N. Buchbinder, and J. Naor, "A Primal-dual randomized algorithm for weighted paging", Proceedings of IEEE Symposium on Foundations of Computer Science, 2007
4. 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, 1997
5. J. Hastad, "Some Optimal Inapproximability Results", Journal of the ACM (JACM), Vol. 48, Issue 4, pages 798-859, July 2001
6. 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
7. Muthukrishnan, "Data Streams: Algorithms and Applications", in Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages: 413-413, 2003
8. P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan, "Approximating Extent Measures of Points", Journal of the ACM (JACM), Vol. 51, No. 4, pages 606-635, 2004
9. 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, 2006
10. J. Chen, H. R. Hsu, K. H. Chuang, C. L. Yang, A. C. Pang, and T. W. Kuo, "Multiprocessor Energy-Efficient Scheduling with Task Migration Considerations", EuroMicro Conference on Real-Time Systems (ECRTS), pages 101-108, 2004.
11. C. M. Hung, J. J. Chen, and T. W. Kuo, "Energy-Efficient Real-Time Task Scheduling for a DVS System with a Non-DVS Processing Element", in IEEE Real-Time Systems Symposium (RTSS), 2006
12. R. L. Graham, "Bounds on Multiprocessing Time Anomalies", SIAM Journal of Applied Mathematics, pages 416-429, 1969
13. M. R. Garey and R. L. Graham, "Bounds for Multiprocessor Scheduling with Resource Constraints", SIAM Journal of Computing, pages 187-200, 1975
14. D. Karger, C. Stein, and J. Wein, "Scheduling Algorithms", a chapter written for the CRC Handbook on Algorithms, 1997
15. J. Remmy, "Resource Constrainned Scheduling on Multiple Machines", Information Processing Letters, pages 177-182, 2004. (Examine this paper.)
Tentative Grading:
Assignments (20%)
Two presentations (40%)
Academic Honesty:
Disability Statement: