diff 6d37dde..626fd2d k_server_squared_log_v2.txt
diff --git a/k_server_squared_log_v2.txt b/k_server_squared_log_v2.txt index 02b732e..b163013 100644 --- a/k_server_squared_log_v2.txt +++ b/k_server_squared_log_v2.txt @@ -1,55 +1,20 @@ ======================================================================== RANDOMIZED K-SERVER IN THE PLANE... NO WAIT, IN ANY SPACE AT ALL: WHY THE BEST GUARANTEE IS ABOUT (LOG K) SQUARED - A friendly, complete tour for a smart high-school reader + ======================================================================== by way of explanation of the paper "Squared-logarithmic randomized k-server on arbitrary metrics" -(the main theorem, the ideas, and the proof architecture) -This document is written so that a curious high-school student can -read it from beginning to end and understand what the paper proves -and how it proves it. Every technical term is defined when it first -appears. Nothing is hand-waved. A short glossary at the end repeats -the notation. -If you know what a set is, what distance means on a number line, -what an average is, what log base 2 means, and what "power of 2" -means, you can read this. You do NOT need to know any graduate -mathematics. + All logarithms in the original paper are natural logarithms (base e). Changing to base 2 multiplies every log by a fixed number 1/ln 2 and does not change any "order of growth" statement. Where a reader may prefer base 2, we say so. ------------------------------------------------------------------------- -CONTENTS ------------------------------------------------------------------------- - 0. A 60-second summary - 1. What is the k-server problem? - 2. Competitive ratio: how we grade an online strategy - 3. Randomness, and the oblivious adversary - 4. The history: from k to (2k-1) to log k to log^2 k - 5. The main theorem, stated in plain English - 6. The big picture: how the proof is built - 7. The game board: metrics, servers, costs - 8. Lazy simulation: why we can copy a virtual solution - 9. Hidden optimal solutions and their shadow (posterior measure) -10. The tree: approximations by hierarchically separated trees -11. The allocation theorem: sharing k units up a tree -12. The pilot potential: a brake for changing partitions -13. Online partitions: heavy balls and chronological rosters -14. Parked mass and moving anchors: paying for reused labels -15. Rounding: from fractional mass to integer servers -16. Transfer: from one law to one policy on any space -17. Assembling the final bound: where each log lives -18. Honest limits: what the paper does NOT claim -19. A one-page glossary -20. A how-to-read-the-paper map - ------------------------------------------------------------------------- 0. A 60-SECOND SUMMARY ------------------------------------------------------------------------