Lower Bound for the Deterministic Competitiveness of a Metrical Task System Apr 3 08:42 2002 Theorem. Let M be any metric space of cardinality n. Then there is a set of tasks calT on M such that there is no deterministic online algorithm which is less than 2n-1 competitive for (M,calT). Proof: Let x_1, ... x_n be the states. Assume that x_1 is the start state. Let calT be the set of all non-negative functions from M to Reals. Let calA be any deterministic online algorithm for M. Without loss of generality, all distances in M are at least 1. Let epsilon be a small positive number. Let {iota_i} be the request vector where iota_i(x_i) = epsilon, and iota_i(x_j) = 0 for all j not equal to i. We define the "cruel request sequence" to be the request sequence which requests the task iota_i if the current state of calA is x_i. We will now define 2n-1 offline algorithms, calB_1 ... calB_{2n-1}. Except for the very first request, the total cost for all of these offline algorithm algorithms is equal to the cost for calA. It follows that, asymptotically, calA pays at least 2n-1 times as much as some calB_i. We call calB_1 ... calB_n the "stubborn" offline algorithms, and the others the "movable" offline algorithms. The first request will be iota_1. For 1 <= i <= n, calB_i moves immediately to x_i upon the first request, and then never leaves that state. For n < i <= 2n-1, calB_i moves to x_{i-n+1} upon the first request, and afterwards behaves so as to maintain the following invariant: At the end of each step, there are exactly two algorithms in each state. In particular, there is one stubborn offline algorithm in each state, and there is one movable offline algorithm in each state except for calA's current state. This invariant can be realized as follows. If, in response to a request, calA does not change state, then none of the calB_i change state. If calA changes state from x_i to x_j in response to the request iota_i, then the one movable offline algorithm that was at state x_j first serves the request, then moves to x_i. Note that, except for the initial step where the calB_i get into position, the total cost of all the calB_i at each step is precisely the cost of calA at that step. The theorem follows.