COMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMS

Abstract

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number Of stacks n is 2. Furthermore the competitive ratio found here is a low bound if the Garwick's algorithm is also & competitive algorithm for n greater-than-or-equal-to 3.