CS 795 Fall 2008
Approximation Algorithms

Lecture Time: Thursday 4:30 pm - 7:10 pm
Location: Innovation Hall 134
Course webpage: http://www.cs.gmu.edu/~lifei/teaching/cs795_fall08/
Credit: 3

Instructor: Fei Li, Office 443 ST II, email:
Office hours: Friday 4:00pm - 6:00pm

NEW:

 

Course Overview:

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.

Prerequisites:

CS 583 or equivalent, or permission of the instructor. Please contact with the instructor if you are not sure.

Recommended Books:

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

Course Materials: (Tentative)

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

Paper List (Papers are to be added in this list along the course):

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:

1. Assignments (20%)

2. Two presentations (40%)

3. A project. You can work on designing and analyzing an approximation algorithms for a NP-hard problem or you can implement some known approximation algorithms for some specific applications, and provide experimental analysis. (40%)

 

Academic Honesty:

 

The integrity of the University community is affected by the individual choices made by each of us. GMU has an Honor Code with clear guidelines regarding academic integrity. Three fundamental and rather simple principles to follow at all times are that: (1) all work submitted be your own; (2) when using the work or ideas of others, including fellow students, give full credit through accurate citations; and (3) if you are uncertain about the ground rules on a particular assignment, ask for clarification. No grade is important enough to justify academic misconduct. Plagiarism means using the exact words, opinions, or factual information from another person without giving the person credit. Writers give credit through accepted documentation styles, such as parenthetical citation, footnotes, or endnotes. Paraphrased material must also be cited, using MLA or APA format. A simple listing of books or articles is not sufficient. Plagiarism is the equivalent of intellectual robbery and cannot be tolerated in the academic setting. If you have any doubts about what constitutes plagiarism, please see me.

 

Disability Statement:

 

If you have a learning or physical difference that may affect your academic work, you will need to furnish appropriate documentation to the Disability Resource Center. If you qualify for accommodation, the DRC staff will give you a form detailing appropriate accommodations for your instructor. In addition to providing your professors with the appropriate form, please take the initiative to discuss accommodation with them at the beginning of the semester and as needed during the term. Because of the range of learning differences, faculty members need to learn from you the most effective ways to assist you. If you have contacted the Disability Resource Center and are waiting to hear from a counselor, please tell me.