diff 9506729..2bdbbf5 k_server_squared_log_v2.txt
diff --git a/k_server_squared_log_v2.txt b/k_server_squared_log_v2.txt index b3a2ca7..ee8319d 100644 --- a/k_server_squared_log_v2.txt +++ b/k_server_squared_log_v2.txt @@ -15,42 +15,7 @@ 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. -0. A 60-SECOND SUMMARY ------------------------------------------------------------------------- - -Imagine k taxi drivers in a city. Customers call in one at a time -and each call must be sent a taxi. You must drive some taxi to the -customer and every meter driven costs you. You do NOT know future -calls. You must decide online. - -The k-server problem is the clean mathematical form of this. The -"city" is any metric space (any set with a distance function obeying -the triangle inequality). You have k "servers" at points of that -space. A request arrives at a point of the space, and one server -must visit it, moving any distance. The total distance moved is the -cost. - -The paper answers a fundamental question. If an all-knowing referee -had seen the entire request sequence in advance, they could have -planned the cheapest possible set of taxi trips. Call their total -cost OPT. The paper shows: - - There is ONE randomized online strategy such that, for ANY metric - space, ANY starting positions of the k servers, and ANY sequence - of requests, the expected cost is at most - - C * (1 + log(k+1))^2 * OPT + B, - - where C is a fixed absolute number (not depending on the metric, - on k, on the starting positions, on the sequence, or on its - length), and B is a finite number that may depend on the metric, - k, and the starting positions, but not on the requests. If the - starting positions are distinct, B can be taken to be 0. -That is the headline. The rest of this document explains what every -word in that sentence means, why the exponent 2 is correct (it is -the best possible in the worst case; a lower bound of the same -shape is known), and how the proof is built. ------------------------------------------------------------------------ 1. WHAT IS THE K-SERVER PROBLEM? @@ -499,7 +464,7 @@ servers start on the same point, because a "shadow" simulation is exact in every input. ------------------------------------------------------------------------ -5. THE MAIN THEOREM, STATED IN PLAIN ENGLISH +5. THE MAIN THEOREM ------------------------------------------------------------------------ Here is the paper's headline theorem, fully precise.