完整後設資料紀錄
DC 欄位語言
dc.contributor.authorCHIEN, BCen_US
dc.contributor.authorCHEN, RJen_US
dc.contributor.authorYANG, WPen_US
dc.date.accessioned2019-04-02T05:59:16Z-
dc.date.available2019-04-02T05:59:16Z-
dc.date.issued1992-01-01en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/11536/149109-
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.department資訊科學與工程研究所zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.contributor.departmentInstitute of Computer Science and Engineeringen_US
dc.identifier.wosnumberWOS:A1992LF70500010en_US
dc.citation.woscount0en_US
顯示於類別:期刊論文