Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Suppose that k mobile servers are located on a circle. Repeatedly, a request at a point x on the circle appears. To serve this request one of the servers has to be moved to x. The cost of moving a server to x is the distance on the circle between the server's previous location and x. The decision which server to move has to be done on-line; that is, without the knowledge of future requests. We give a deterministic on-line algorithm for making these decisions. Our algorithm is O(k3)-competitive: for any sequence of requests, the cost incurred by our algorithm in serving this sequence is bounded (up to an additive constant) by O(k3) times the cost of serving this sequence using the best off-line algorithm; i.e., an algorithm that has a priori knowledge of the whole sequence. Our algorithm is the best deterministic constructive algorithm for k>2. © 1994 Springer-Verlag New York Inc.
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
J. LaRue, C. Ting
Proceedings of SPIE 1989