Gourds will fly: Rowan University American Society of Mechanical Engineers to host fifth annual Pumpkin Chunkin’ |

More
Hail to the Profs! Homecoming 2014 in pictures |

More
Second biennial ScholarFest to celebrate Rowan research |

More
Rowan hosts talk on “Controlling Ebola Virus Outbreaks: A New Strategy to Block Virus Transmission and Spread” |

More
Prof pride: Alumni flock to campus for Homecoming |

More
Technical Report Number TR1995-3

Title

On Space Bounded Server Algorithms

Authors

Ganesh Baliga

Department of Computer Science

Rowan College of New Jersey

Glassboro, NJ 08028

Steven Hughes

Department of Computer Science

Indiana University

Bloomington, IN

Anil M. Shende

Dept. of Mathematics, Computer Science & Physics

Roanoke College

Salem, VA 24153

Abstract

This paper studies space bounded algorithms, i.e., algorithms that use

a constant amount of scratch space, for the k-server problem. The

paper first shows a characterization of the set of space bounded

algorithms that are competitive in finite metric spaces. The result

yields a method for (1) effectively deciding if a given space bounded

algorithm is competitive in a given finite metric space, and (2) for

designing competitive space bounded algorithms in finite metric

spaces.

The above results are then refined, in particular using the geometry

of metric spaces, to develop two methods for obtaining an upper bound

on competitive factors of arbitrary space bounded algorithms. One of

these methods is then used to show that any algorithm, employing the

Least Recently Used strategy, is linearly competitive on a uniform

metric space.