The CNN problem and other \(k\)-server variants (Q1887095)

We study several interesting variants of the \(k\)-server problem. In the CNN problem, one server services requests in the Euclidean plane. The difference from the \(k\)-server problem is that the server does not have to move to a request, but it has only to move to a point that lies in the same horizontal or vertical line with the request. This, for example, models the problem faced by a crew of a certain News Network trying to shoot scenes on the streets of Manhattan from a distance; for any event at an intersection, the crew has only to be on a matching street or avenue. The CNN problem contains as special cases two important problems: the BRIDGE problem, also known as the cow-path problem, and the weighted 2-server problem in which the 2 servers may have different speeds. We show that any deterministic online algorithm has competitive ratio at least \(6 + \sqrt 17\). We also show that some successful algorithms for the \(k\)-server problem fail to be competitive. In particular, no memoryless randomized algorithm can be competitive.We also consider another variant of the\(k\)-server problem, in which servers can move simultaneously, and we wish to minimize the time spent waiting for service. This is equivalent to the regular \(k\)-server problem under the \(L_\infty\) norm for movement costs. We give a \(\frac 12k(k + 1)\) upper bound for the competitive ratio on trees.