Full metadata record
DC FieldValueLanguage
dc.contributor.authorCHIEN, BCen_US
dc.contributor.authorCHEN, RJen_US
dc.contributor.authorYANG, WPen_US
dc.date.accessioned2014-12-08T15:05:03Z-
dc.date.available2014-12-08T15:05:03Z-
dc.date.issued1992en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/11536/3583-
dc.description.abstractAn 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.en_US
dc.language.isoen_USen_US
dc.titleCOMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMSen_US
dc.typeArticleen_US
dc.identifier.journalLECTURE NOTES IN COMPUTER SCIENCEen_US
dc.citation.volume650en_US
dc.citation.spage78en_US
dc.citation.epage87en_US
dc.contributor.department資訊科學與工程研究所zh_TW
dc.contributor.departmentInstitute of Computer Science and Engineeringen_US
dc.identifier.wosnumberWOS:A1992BY27R00010-
dc.citation.woscount0-
Appears in Collections:Articles