ICS 280
Online Algorithms
Spring 2002

Time: Mondays and Wednesdays, 2:00PM - 3:30PM
Location: CS249
Professor: Sandy Irani, 352D, 824-6346
Email: irani@ics.uci.edu

Course Goals and Description

The field of online algorithms addresses situations where the input to a problem is received incrementally through time and an algorithm must make computational decisions based on only a portion of the input. Many fundamental problems arising in computer systems are online problems. We start with an introduction to competitive analysis, our principle means of analyzing and evaluating online algorithms. We will analyze algorithms for online problems in a variety of application areas as well as explore alternative measures for optimization with incomplete information.

Course Requirements

A class project and several (3 or 4) sets of homework exercises will be required. The project can be a theoretical result, an empirical study or a survey paper. Each student is required to give a brief presentation on his or her project in class. (40-50)% of the class grade will be based on homework exercises and the rest will be based on the project.

Reading

The reading for the course will consist mainly of research and survey papers from journals and conference proceedings.

Specific Topics and Papers:

Paging

Competitive analysis of deterministic algorithms

On Online Computation, Sandy Irani and Anna R. Karlin, from Approximation Algorithms for NP-hard Problems, ed., Dorit Hochbaum.

Competitive analysis of randomized algorithms
- From On Online Computation
Probabilistic Analysis of Paging
- IP over connection-oriented networks and distributional paging, Lund, C.; Phillips, S.; Reingold, N., Proceedings. 35th Annual Symposium on Foundations of Computer Science, 1994. p. 424-34.
Paging with Locality of Reference
- On Paging with Locality of Reference S. Albers, L.M. Favrholdt and O. Giel, To appear in Proceedings. 34th Annual Symposium on the Theory of Computing, 2002.
- Truly Online Paging with Locality of Reference. A. Fiat, M. Mendel. Proceedings. 38th Annual Symposium on Foundations of Computer Science, 1997.
Variations on Paging
- Web Caching with Request Reordering T. Feder, R. Motwani, R. Panigrahy, and A Zhu. Proceedings of the 13th Annual Symposium on Discrete Algorithms, 2002, pages 104-105.
- Caching with Expiration Times P. Gopalan, H. Karloff, A. Mehta, M. Mihail, and N. Vishnoi. Proceedings of the 13th Annual Symposium on Discrete Algorithms, 2002, pages 540-547.

Web Caching

Cost-Aware WWW Proxy Caching Algorithms P. Cao and S. Irani, In the Proceedings of the USENIX Symposium on Internet Technologies and Systems, 1997.
Caching Documents with Variable Sizes and Prefetching Costs: an LP-Based Approach. E. Cohen and H. Kaplan. In Proc. 10th ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, 1999.

Connection Caching

Connection caching: model and algorithms. E. Cohen, H. Kaplan, and U. Zwick. J. Comput. System Sci. , 2002. To appear.
Connection caching under various models of communication. E. Cohen, H. Kaplan, and U. Zwick. In Proc. 12th Annual ACM Symposium on Parallel Algorithms and Architectures. ACM, 2000.

Ski Rental Revisited

Dynamic TCP acknowledgement and other stories about e/(e-1). A.R. Karlin, C. Kenyon and D. Randall. 33rd Symposium on Theory of Computing (STOC): 502--509, 2001.
Competitive Analysis of Dynamic Power Management Strategies for Systems with Multiple Power Saving States. S. Irani, S. Shukla, R. Gupta. Submitted for publication.

Online Algorithms over the Internet: the Applications Level

Query strategies for priced information. M. Charikar, R. Fagin, V. Guruswami, J. Kleinberg, P. Raghavan, A. Sahai. Proc. 32nd ACM Symposium on Theory of Computing, 2000.
Online Auctions

Competitive Auctions and Digital Goods A. Goldberg, J. Hartline and A. Wright. In Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM, 2001.
Competitive Generalized Auctions A. Fiat, A. Goldberg, J. Hartline, and A. Karlin. To appear in the Proc. 34th ACM Symposium on Theory of Computing, 2002.

Routing, Game Theory and Competitive Analysis

Worst-case Equilibria E. Koutsoupias and C. Papadimitriou. Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pp 404-413.
How Bad is Selfish Routing? T. Roughgarden and E. Tardos. Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science, 2000.
Optimization Problems in Congestion Control. Karp, Koutsoupias, Papadimitriou, Shenker. Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science, 2000.
A Randomized Online Algorithm for Bandwidth Utilization. Sanjeev Arora and Bo Brinkman. in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 535-539, 2002.

General Online Algorithms

A Guessing Game and Randomized Online Algorithms. S. Seiden. In Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, May 2000, pp. 592-601.

Switches, Buffers and Streaming

Nearly Optimal FIFO Buffer Management for DiffServ. Z. Lotker, B. Patt-Shamir.
Buffer Overflow Management in QoS Switches . A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Scheiber, M. Sviridenko. 33rd Symposium on Theory of Computing (STOC): 520--529, 2001.
Online Server Allocation in a Server Farm via Benefit Task System. T. S. Jayram, T. Kimbrel, R. Krauthgamer, B. Schieber, in Proceedings of Symposium on Theory of Computing (STOC 01), pp. 540--549.
Competitive On-line Switching Policies. A. Bar-Noy, A. Freund, S. Landa, and J. (S.) Naor. Extended Abstract: Proc. 13th Symposium on Discrete Algorithms (SODA02), pp. 525-534, 2002.

ICS 280 Online Algorithms Spring 2002