Elias Koutsoupias / Publications

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.

@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}
}