Title :
On space bounded server algorithms
Author :
Baliga, Ganesh R. ; Shende, Anil M.
Author_Institution :
Dept. of Comput. & Inf. Sci., Delaware Univ., Newark, DE, USA
Abstract :
This paper is motivated by the need for fast algorithms for online problems, many of which require algorithms to provide solutions in real time. We study a class of arguably fast algorithms (called space bounded algorithms) for the k-server problem on finite metric spaces. Specifically, we provide a necessary and sufficient condition for such algorithms to be competitive on finite metric spaces. Moreover, this characterization provides a strategy for designing competitive algorithms for finite metric spaces
Keywords :
algorithm theory; network servers; online operation; real-time systems; competitive algorithm design; fast algorithms; finite metric spaces; k-server problem; necessary condition; online problems; real-time solutions; space bounded algorithms; sufficient condition; Algorithm design and analysis; Computational Intelligence Society; Computer science; Cost function; Extraterrestrial measurements; Processor scheduling; Scheduling algorithm;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315400
