### 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 a competitive algorithm for n > 3.

Original language | English |
---|---|

Title of host publication | Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings |

Editors | Takao Nishizeki, Toshihide Ibaraki, Kazuo Iwama, Masafurni Yamashita, Yasuyoshi Inagaki |

Publisher | Springer Verlag |

Pages | 78-87 |

Number of pages | 10 |

ISBN (Print) | 9783540562795 |

DOIs | |

State | Published - 1 Jan 1992 |

Event | 3rd International Symposium on Algorithms and Computation, ISAAC 1992 - Nagoya, Japan Duration: 16 Dec 1992 → 18 Dec 1992 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 650 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 3rd International Symposium on Algorithms and Computation, ISAAC 1992 |
---|---|

Country | Japan |

City | Nagoya |

Period | 16/12/92 → 18/12/92 |

## Fingerprint Dive into the research topics of 'Competitive analysis of the on-line algorithms for multiple stacks systems'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings*(pp. 78-87). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 650 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56279-6_60