{"data":{"id":"10.48550/arxiv.cs/0205038","type":"dois","attributes":{"doi":"10.48550/arxiv.cs/0205038","prefix":"10.48550","suffix":"arxiv.cs/0205038","identifiers":[{"identifier":"cs/0205038","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"cs/0205038"}],"creators":[{"name":"Fiat, Amos","nameType":"Personal","givenName":"Amos","familyName":"Fiat","affiliation":[],"nameIdentifiers":[]},{"name":"Karp, Richard","nameType":"Personal","givenName":"Richard","familyName":"Karp","affiliation":[],"nameIdentifiers":[]},{"name":"Luby, Mike","nameType":"Personal","givenName":"Mike","familyName":"Luby","affiliation":[],"nameIdentifiers":[]},{"name":"McGeoch, Lyle","nameType":"Personal","givenName":"Lyle","familyName":"McGeoch","affiliation":[],"nameIdentifiers":[]},{"name":"Sleator, Daniel","nameType":"Personal","givenName":"Daniel","familyName":"Sleator","affiliation":[],"nameIdentifiers":[]},{"name":"Young, Neal E.","nameType":"Personal","givenName":"Neal E.","familyName":"Young","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Competitive Paging Algorithms"}],"publisher":"arXiv","container":{},"publicationYear":2002,"subjects":[{"lang":"en","subject":"Data Structures and Algorithms (cs.DS)","subjectScheme":"arXiv"},{"lang":"en","subject":"Networking and Internet Architecture (cs.NI)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"lang":"en","subject":"F.2.0; F.1.2; C.0","subjectScheme":"ACM"}],"contributors":[],"dates":[{"date":"2002-05-18T13:49:31Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2015-06-02T00:08:22Z","dateType":"Updated","dateInformation":"v1"},{"date":"2002-05","dateType":"Available","dateInformation":"v1"},{"date":"2002","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1016/0196-6774(91)90041-v","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004","rightsUri":"http://arxiv.org/licenses/assumed-1991-2003/"}],"descriptions":[{"description":"The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. This paper introduces the marking algorithm, a simple randomized on-line algorithm for the paging problem, and gives a proof that its performance guarantee (competitive ratio) is O(log k). In contrast, no deterministic on-line algorithm can have a performance guarantee better than k.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi5DUy8wMjA1MDM4PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+Y3MvMDIwNTAzODwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5GaWF0LCBBbW9zPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5BbW9zPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkZpYXQ8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+S2FycCwgUmljaGFyZDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+UmljaGFyZDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5LYXJwPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkx1YnksIE1pa2U8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPk1pa2U8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+THVieTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5NY0dlb2NoLCBMeWxlPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5MeWxlPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPk1jR2VvY2g8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+U2xlYXRvciwgRGFuaWVsPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5EYW5pZWw8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+U2xlYXRvcjwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5Zb3VuZywgTmVhbCBFLjwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+TmVhbCBFLjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Zb3VuZzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+Q29tcGV0aXRpdmUgUGFnaW5nIEFsZ29yaXRobXM8L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMDI8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5EYXRhIFN0cnVjdHVyZXMgYW5kIEFsZ29yaXRobXMgKGNzLkRTKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPk5ldHdvcmtpbmcgYW5kIEludGVybmV0IEFyY2hpdGVjdHVyZSAoY3MuTkkpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJBQ00iPkYuMi4wOyBGLjEuMjsgQy4wPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwMi0wNS0xOFQxMzo0OTozMVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxNS0wNi0wMlQwMDowODoyMlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDAyLTA1PC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJUZXh0Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHJlbGF0ZWRJZGVudGlmaWVycz4KICAgIDxyZWxhdGVkSWRlbnRpZmllciByZWxhdGVkSWRlbnRpZmllclR5cGU9IkRPSSIgcmVsYXRpb25UeXBlPSJJc1ZlcnNpb25PZiI+MTAuMTAxNi8wMTk2LTY3NzQoOTEpOTAwNDEtVjwvcmVsYXRlZElkZW50aWZpZXI+CiAgPC9yZWxhdGVkSWRlbnRpZmllcnM+CiAgPHZlcnNpb24+MTwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL2Fzc3VtZWQtMTk5MS0yMDAzLyI+QXNzdW1lZCBhclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2UgdG8gZGlzdHJpYnV0ZSB0aGlzIGFydGljbGUgZm9yIHN1Ym1pc3Npb25zIG1hZGUgYmVmb3JlIEphbnVhcnkgMjAwNDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPlRoZSBwYWdpbmcgcHJvYmxlbSBpcyB0aGF0IG9mIGRlY2lkaW5nIHdoaWNoIHBhZ2VzIHRvIGtlZXAgaW4gYSBtZW1vcnkgb2YgayBwYWdlcyBpbiBvcmRlciB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIHBhZ2UgZmF1bHRzLiBUaGlzIHBhcGVyIGludHJvZHVjZXMgdGhlIG1hcmtpbmcgYWxnb3JpdGhtLCBhIHNpbXBsZSByYW5kb21pemVkIG9uLWxpbmUgYWxnb3JpdGhtIGZvciB0aGUgcGFnaW5nIHByb2JsZW0sIGFuZCBnaXZlcyBhIHByb29mIHRoYXQgaXRzIHBlcmZvcm1hbmNlIGd1YXJhbnRlZSAoY29tcGV0aXRpdmUgcmF0aW8pIGlzIE8obG9nIGspLiBJbiBjb250cmFzdCwgbm8gZGV0ZXJtaW5pc3RpYyBvbi1saW5lIGFsZ29yaXRobSBjYW4gaGF2ZSBhIHBlcmZvcm1hbmNlIGd1YXJhbnRlZSBiZXR0ZXIgdGhhbiBrLjwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/cs/0205038","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-19T02:34:23.000Z","registered":"2022-03-19T02:34:24.000Z","published":"2002","updated":"2022-03-19T02:34:24.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.cs/0205038","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}