@inproceedings{d0f43716a5ec431995e4f1528aededa4,

title = "Competitive analysis of the on-line 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{\textquoteright}s algorithm is not a competitive algorithm, but Garwick{\textquoteright}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{\textquoteright}s algorithm is also a competitive algorithm for n > 3.",

author = "Chien, {Been Chian} and Rong-Jaye Chen and Yang, {Wei Pang}",

year = "1992",

month = jan,

day = "1",

doi = "10.1007/3-540-56279-6_60",

language = "English",

isbn = "9783540562795",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "78--87",

editor = "Takao Nishizeki and Toshihide Ibaraki and Kazuo Iwama and Masafurni Yamashita and Yasuyoshi Inagaki",

booktitle = "Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings",

address = "Germany",

note = "null ; Conference date: 16-12-1992 Through 18-12-1992",

}