標題: COMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMS
作者: CHIEN, BC
CHEN, RJ
YANG, WP
資訊工程學系
資訊科學與工程研究所
Department of Computer Science
Institute of Computer Science and Engineering
公開日期: 1-Jan-1992
摘要: 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.
URI: http://hdl.handle.net/11536/149109
ISSN: 0302-9743
期刊: LECTURE NOTES IN COMPUTER SCIENCE
Volume: 650
起始頁: 78
結束頁: 87
Appears in Collections:Articles