The CNN Problem and Other k-Server Variants

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