How to read: "The On-Line K-Server Problem," by Aris Foratos and Ravi Boppana. LAST UPDATE: Tue Dec 5 10:16:36 PST 2006 There is a tendency for people to stop reading a paper when they "stall" over material they don't understand. This can be a mistake, as the "hardness" of a manuscript can fluctuate. Thus, I will give you some guidance, as well as some hints, and even errata. 1. Download the file (it is in PDF) and print it out. 2. Mark the paper as follows. A. The definition of "metric space" on page 3 is not the usual one. The definition of "symmetric metric space" in this paper is the same as the usual definition of "metric space." B. Draw a horizontal line on page 9, just above "Definition 3.3"; we will call this "Line 1." C. Mark all text between the beginning of the manuscript and Line 1 GREEN. D. Draw a horizontal line on page 11, just above "3.2 The HARMONIC"; we will call this "Line 2." E. Draw a horizontal line on page 12, just above the beginning of the paragraph that starts "The proof"; we will call this "Line 3." F. Mark all text between Line 2 and Line 3 GREEN. G. Draw a horizontal line on page 16 just above the paragraph that starts with "Although this result"; we call this "Line 4" H. Draw a horizontal line on page 19 just below the first line, "Lemma 4.2 ROTATE is k-competitive"; we call this "Line 5." I. Mark all text between Line 4 and Line 5 GREEN. J. Draw a horizontal line on page 20 just above "4.3 MARKING"; we call this "Line 6." K. Draw a horizontal line on page 20 just above "Proof:"; we call this "Line 7." L. Mark all text between Line 6 and Line 7 GREEN. M. Draw a horizontal line on page 21 just above "MARKING was the"; we call this "Line 8." N. Draw a horizontal line on page 22 just above the paragraph that starts with "The algorithm is based"; we call this "Line 9." O. Mark all text between Line 8 and Line 9 GREEN. P. Draw a horizontal line on page 25 just above "4.5 RANDOM"; we call this "Line 10." Q. Draw a horizontal line on page 25 just above "Proof:"; we call this "Line 11." R. Mark all text between Line 10 and Line 11 GREEN. S. Draw a horizontal line on page 26 just above the paragraph that starts with "As mentioned at"; we call this "Line 12." T. Draw a horizontal line on page 27 just above "Proof:"; we call this "Line 13." U. Mark all text between Line 12 and Line 13 GREEN. V. Draw a horizontal line the bottom of page 29; we call this "Line 14." W. Error: On line 9 of page 30, change "d(q,p)" to "d(p,q)." X. Draw a horizontal line on page 30 just above "Proof:"; we call this "Line 15." Y. Mark all text between Line 14 and Line 15 GREEN. Z. Draw a horizontal line on page 32 just above "8 Lower Bounds"; we call this "Line 16." AA. Draw a horizontal line on page 32 just above "Proof:"; we call this "Line 17." AB. Mark all text between Line 16 and Line 17 GREEN. AC. Draw a horizontal (sort of) line on page 35 just before the word "Furthermore" on line -15; we call this "Line 18." AD. Draw a horizontal line on page 35 just below Lemma 8.3; we call this "Line 19." AE. Mark all text between Line 18 and Line 19 GREEN. AF. Draw a horizontal line on page 36 just above "9 Conclusion"; we call this "Line 20." AG. Mark all text between Line 20 and the end of the paper GREEN. 3. For your first reading, read all text marked GREEN. You should be done by Tuesday, December 5. If you hit a rough spot, keep reading; then go back to the rough spot. ------------ 4. Second Reading. A. Read from the beginning of the paragraph starting with "Karloff" on page 33 to the end of the statement of Lemma 8.2 on page 34. B. Read Lemma 8.5 on page 36, and the four-line paragraph just after the lemma.