CS 795 Spring 2008
Online Algorithms

Lecture Time: Monday 7:20pm - 10:00pm
Location: Robinson Hall A 243
Course webpage: http://www.cs.gmu.edu/~lifei/teaching/cs795_spring08/
Credit: 3

Instructor: Fei Li, Office 443 ST II, Email: lifei@cs.gmu.edu
Office hours: Monday 5:00pm - 7:00pm

NEW:

There is no class on January 21, 2008.

Course Overview:

In this course, we will learn deterministic and randomized online algorithms and their analysis. This course covers 2 parts. In the first part, we will introduce the basic concepts on online algorithms and competitive analysis. We will cover some classic online algorithms and their analysis, including list scheduling, paging algorithms, k-server problems, online scheduling, potential functions and Yao's principle for lower bounds. We will also introduce some applications of online algorithms, such as power saving problems, online searching, online auction, and packet buffering problems, etc. In the second part, we will discuss some recent and important papers appeared in the conferences like STOC, SODA, FOCS, RTSS, ACM-EC, etc. Students are required to make a comprehensive survey and give presentations of those papers in class.

Prerequisites:

CS 483. Please contact with the instructor if you are not sure.

Required Textbook:

Online Computation and Competitive Analysis, BE by Allan Borodin and Ran El-Yaniv

Recommended Books:

Randomized Algorithms, MR (Chapter 2, Chapter 13) by Rajeev Motwani and Prabhakar Raghavan

Introduction to Algorithms, CLRS (Chapter 5, Chapter 17) by Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Algorithm Design, KT (Chapter 13) by Jon Kleinberg and Eva Tardos (You can find a sample copy of Chapter 13 on the webpage.)

Course Materials: (Tentative)

Lecture	Date	Topic	Lecture Notes	Scope
01	January 28	Introduction of potential function		CLSR Ch. 17; CLSR Ch. 5; KT Ch. 13
02	February 4	Introduction of andomized algorithms and zero-sum games		MR Ch. 2; BE Ch. 6, 7, 8
03	February 11	List scheduling		BE Ch. 1, Ch. 2
04	February 18	Paging algorithms		BE Ch. 3, Ch. 4
05	February 25	Paging models and new metrics		BE Ch. 5; SIGACT News
06	March 3	k-server problem		BE Ch. 9, Ch. 10, Ch. 11
	March 10	Spring break
07	March 17	Load balancing and call admission		BE Ch. 12; BE Ch. 13; makespan
08	March 24	Online learning and decision theories		BE Ch. 14; BE Ch. 15; adversary networks
09	March 31	(Discussion) Online scheduling		See papers
10	April 7	(Discussion) Power management		See papers
11	April 14	(Discussion) Packet buffering		See papers
12	April 21	(Discussion) Online search and social networks (TBD)		See papers
13	April 28	Presentations
14	May 5	Presentations

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

• Paging algorithms

  1. G. S. Brodal and R. Fagarberg, On the Limits of Cache-Obliviousness, STOC 03.

  2. J. Boyar, L. M. Favrholdt, and K. S. Larsen, The Relative Worst-order Ratio Applied to Paging, Journal of Computer and System Sciences, 2007.

  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. S. Angelopoulos, R. Dorrigiv, and A. Lopez-Ortiz, On the Separation and Equivalence of Paging Strategies, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2007.

  5. R. Dorrigiv and A. Lopez-Ortiz, Adaptive Analysis of Online Algorithms, Dagstuhl Seminar Proceedings, 06421.

• Online routing

  1. A. Broder, A. Frieze, E. Upfal. A General Approach to Dynamic Packet Routing with Bounded Buffers, IEEE FOCS, 1996.

  2. J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts. Online Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. Journal of the Association for Computing Machinery 44(3):486-504, May 1997.

  3. M. Andrews and L. Zhang. Packet Routing with Arbitrary End-to-End Delay Requirements, STOC 99.

  4. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. Stochastic Models for the Web Graph. In Proceedings of the 41st Annual Symposium on the Foundations of Computer Science, 2000.

• Online scheduling

  1. F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko, Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates, Proceedings of IEEE Conference on Foundation of Computer Science, 1999.

  2. L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, and K. Pruhs, Online Weighted Flow Time and Deadline Scheduling, Proceedings of Approximation, Randomization, and Combinatorial Optimization, 2001.

  3. 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.

  4. C. Chekuri, R. Motwani, B. Natarajan, and C. Stein, Approximation Techniques for Average Completion Time Scheduling, SIAM Journal on Computing, 2001.

  5. C.-Y. Koo, T.-W. Lam, T.-W. Ngan, and K.-K. To, Online Scheduling with Tight Deadlines, Mathematical Foundations of Computer Science, 2001.

  6. J. Sgall, Online Scheduling - A Survey, Chapter, Online Algorithms, 1998.

  7. J. Garay, J. Naor, B. Yener, and P. Zhao, Online Admission Control and Job Scheduling with Preemption, DIMACS Technical Report, 2001.

  8. S. Divakaran and M. Saks, Online Scheduling with Release Times and Set-ups, DIMACS Technical Report, December 2001.

  9. M. Chrobak, W. Jawor, J. Sgall, and T. Tichy, Online Scheduling of Equal-length Jobs: Randomization and Restarts Help, 2004 .

  10. G. Koren and D. Shasha, Competitive Algorithms and Lower Bounds for Online Scheduling of Multiprocessor Real-time Systems, 1993.
  11. R. J. Lipton and A. Tomkins, Online Interval Scheduling, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1994.
  12. C. Phillips, C. Stein, and J. Wein, Minimizing Average Completion Time in the Presence of Release Dates, Mathematics of Operations Research, 1999.
  13. N. Gary and A. Kumar, Minimizing Average Flow Time on Related Machines, ACM Symposium on Theory of Computing, 2006.
  14. D. P. Bunde, Scheduling on a Single Machine to Minimize Total Flow Time with Job Rejections, 2005.

• Packet buffering

  1. N. Andelman, Y. Mansour, and A. Zhu, Competitive Queuing Polices for QoS Switches, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2003.

  2. Y. Bartal, F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, R. Lavi, J. Sgall, and T. Tichy, Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs, Proceedings of Symposium on Theoretical Aspects of Computer Science, 2004.

  3. F. Y. L. Chin and S. P. Y. Fung, Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?, Algorithmica, 2003.

  4. M. Chrobak, W. Jawor, J. Sgall, and T. Tichy, Improved Online Algorithms for Buffer Management in QoS Switches, Proceedings of European Symposium on Algorithms, 2004.

  5. B. Hajek, On the Competitiveness of Online Scheduling of Unit-Length Packets with Hard Deadlines in Slotted Time, Proceedings of Conference on Information Sciences and Systems, 2001.

  6. A. Kesselman, Z. Lotker, Y. Mansour, B. P. Shamir, B. Schieber, and M. Sviridenko, Buffer Overflow Management in QoS Switches, Proceedings of ACM Symposium on Theory of Computing, 2001.

  7. F. Li, J. Sethuraman, and C. Stein, An Optimal Online Algorithm for Packet Scheduling with Agreeable Deadlines, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2005.

  8. F. Li, J. Sethuraman, and C. Stein, Better Online Buffer Management, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2007.

  9. M. Englert and M. Westermann, Considering Suppressed Packets Improves Buffer Management in QoS Switches, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2007.

• Power management

  1. H. L. Chan, W. T. Chan, T. W. Lam, L. K. Lee, K. S. Mak, and P. Wong, Energy Efficient Online Deadline Scheduling, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2007.

  2. R. Jejurikar and R. Gupta, Energy Aware Task Scheduling with Take Synchronization for Embedded Real-time Systems, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2007.

  3. Y. Lu, L. Benini, and G. D. Micheli, Power-aware Operating Systems for Interactive Systems, IEEE Transactions on Very Large Scale Integration Systems, April 2002.

  4. 4. S. Irani and K. R. Pruhs, Algorithmic Problems in Power Management, ACM SIGACT News, 2005.

  5. N. Bansal, K. Pruhs, and C. Stein, Speed Scaling for Weighted Flow Time, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2007.

  6. S. Irani, S. Shukla, and R. Gupta, Online Strategies for Dynamic Power Management in Systems with Multiple Power-Saving States, ACM Transactions on Embedded Computing Systems, August 2003.

• Online optimization

  1. M. Zinkevich, Online Convex Programming and Generalized Infinitesimal Gradient Ascent, ICML 2003.

  2. A. D. Flaxman, A. T. Kalai, and H. B. McMahan, Online Convex Optimization in the Bandit Setting: Gradient Descent Without a Gradient, 2004.

  3. E. Hazen, Efficient Algorithms for Online Convex Optimization and Their Applications, PhD thesis, Princeton University, 2006.

  4. E. Hazen, A. Agarwal, and S. Kale, Logarithmic Regret Algorithms for Online Convex Optimization, In Machine Learning, 2007.

  5. H. B. McMahan and A. Blum, Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary, COLT, 2004

• Other approaches

  1. B. Kalyanasundaram and K. Pruhs, Speed is As Powerful As Clairvoyance, Journal of ACM, 2000.

  2. C. A. Phillips, C. Stein, E. Torng, and J. Wein, Optimal Time-critical Scheduling via Resource Augmentation, Proceedings of ACM Symposium on Theory of Computing, 1997.

  3. R. Dorrigiv and A. Lopez-Ortiz, A Survey of Performance Measures for Online Algorithms, ACM SIGACT News, September, 2005.

  4. M. Chrobak and C. Kenyon-Mathieu, Competitiveness via Doubling, ACM SIGACT News, December 2006.

  5. P. Keskinocak, R. Ravi, and S. Tayur, Scheduling and Reliable Lead-time Quotation for Orders with Availability Intervals and Lead-time Sensitive Revenues, INFORMS Management Science, 2001. [Second link in google]

Tentative Grading:

• A survey on an online problem (30%)
• Two presentations (30%)
• A project. You can work on an online problem and provide theoretical analysis results, which should at least have a little originality in algorithm design. Or you can implement some known online algorithms for some specific applications, and provide experimental analysis. I will give a list of problems soon. (40%)