SYMPOSIUM MINISYMPOSIA

ABSTRACT

Many times in life we are forced to make decisions without any knowledge of how these choices may affect future decisions. Thus, we often find later that we could have made a better decision. This is the dilemma of an on-line problem - how can we make the best decisions despite the fact that we have no idea as to what conditions we will be faced with next? In this paper, we examine one example of an on-line problem, the k-server problem (see [BS93] and [KP94] for recent results and a literature survey). Informally, the k-server problem is to devise an algorithm, that uses k servers, and that, given as input a point in a metric space, schedules at least one of its k servers to move to that point, and then waits for the next request. This model for the problem does not take into account the amount of time it takes servers to move to request points. In this paper, we study the k-server problem with this new restriction - service takes some amount of time. We call this the timed k-server problem. Algorithms for this problem are judged by the time their schedules take to finish service on the entire request sequence and the amount of distance their schedules force the servers to travel. Our model is an extension of the space bounded k-server problem [BS93] and hence includes the practical constraints of a finite metric space and a finite amount of memory.

For the timed k-server problem, we present two algorithms, both based on Graham's list scheduling algorithm [Gra66], and prove their competitiveness with respect to service time and service cost in all finite metric spaces.

References

[BS93] Ganesh R. Baliga and Anil M. Shende. On space bounded server algorithms. In Proceedings of the 5th International Conference on Computing and Information, pages 77-81, 1993.

[Gra66] R.L. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 1966.

[KP94] Elias Koutsoupias and Christos Papadimitriou. On the k-server conjecture. In Proceedings of the Symposium on Theory of Computing, pages 507-511, 1994.

Getting More Information

To obtain more information about the meeting send e-mail to: fscc98@pax.st.usm.edu.

Return to PAX
Return to USM

USM
inquire@delphi.st.usm.edu
Updated
http://pax.st.usm.edu