Potentials for Metrical Task Systems Apr 3 07:06 2002 Let M = (M,calT) be a MTS. M is a metric space, and calT is a set of task vectors, i.e., a set of functions from M to Reals + {infinity}. Write ||x,y|| for the distance from x to y in M. We call the elements of M "states." (In some applications it would be confusing to call a state a "point" as the word "point" is reserved for something else. For example, in the k-server problem, a "state" is an unordered k-tuple of "points.") Let W be the set of all work functions on M. Each w in W is a function from M to Reals, which satisfies the 1-Lipschitz condition, namely that w(x) <= w(y) + ||x,y|| for any x,y. We say that w is "supported" by a set S subseteq M if, for any x in M, there exists y in S such that w(x) = w(y) + ||x,y||. If M is finite (and in most practical applications even if M is infinite) there is a unique "minimal support" for any work function. If the minimal support of w consists of a single state x, we say that w is a "cone at x." Sometimes we say that w is "the cone at x," meaning that it is supported by x and that w(x) = 0. If w is a work function and r in calT is a request, the work function w' = w update r is defined by: w'(x) = min_{y in M}(w(y) + ||y,x||). The initial work function w^0 is the cone at the start state. The traditional definition of the work function at step t is w^t = w^{t-1} update r^t. Theorem: Given a request sequence of length n, the optimal cost to service that request sequence is min_{x in M}w^n(x). Proof: Standard dynamic programming. We define a "C-potential" to be a function Phi(w,x) in Reals, defined for every work function w and every state x, such that the following two conditions hold: 1. Update condition. For any work function w, state x, and request r, let w' = w update r. Then there exists a state y such that: Phi(w,x) >= ||x,y|| + r(y) + Phi(w',y) 2. Offset condition. For any work function w, state x, and constant K: Phi(w,x) = Phi(w+K,x) + C*K Theorem: There exists a C-competitive deterministic online algorithm for M if and only if there exists a C-potential. Warning: Technically, we need additional conditions on M. If M is finite, there is no problem. The Theorem also usually holds for classic applications, such as the server problem. In practice, you don't have to worry about those conditions.