E. Koutsoupias and D. S. Taylor.

**The CNN problem and other k-server variants.**In*Theoretical Computer Science*, 324(2-3):347--359, September 2004.### Abstract

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 k(k+1)/2 upper bound for the competitive ratio on trees.### Bib

@Article{KT04, author = {E. Koutsoupias and D. S. Taylor}, title = {The CNN problem and other k-server variants}, journal = {Theoretical Computer Science}, year = {2004}, volume = {324}, number = {2-3}, pages = {347--359}, month = {20 } # sep, note = {An early version appeared in STACS 2000}, } @string{STACS00 = {17th Annual Symposium on Theoretical Aspects of Computer Science}} @InProceedings{KT00, author = {E. Koutsoupias and D. S. Taylor}, title = {The {CNN} Problem and Other $k$-Server Variants}, booktitle = STACS00, year = 2000, month = {17--19 } # feb, pages = {581--592}, address = {Lille, France}, note = {To appear in Theoretical Computer Science} }