Competitive analysis of the on-line algorithms for multiple stacks systems

Been Chian Chien, Rong-Jaye Chen, Wei Pang Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationAlgorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings
EditorsTakao Nishizeki, Toshihide Ibaraki, Kazuo Iwama, Masafurni Yamashita, Yasuyoshi Inagaki
PublisherSpringer Verlag
Pages78-87
Number of pages10
ISBN (Print)9783540562795
DOIs
StatePublished - 1 Jan 1992
Event3rd International Symposium on Algorithms and Computation, ISAAC 1992 - Nagoya, Japan
Duration: 16 Dec 199218 Dec 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume650 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Symposium on Algorithms and Computation, ISAAC 1992
CountryJapan
CityNagoya
Period16/12/9218/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

    Chien, B. C., Chen, R-J., & Yang, W. P. (1992). Competitive analysis of the on-line algorithms for multiple stacks systems. In T. Nishizeki, T. Ibaraki, K. Iwama, M. Yamashita, & Y. Inagaki (Eds.), 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