{"entities":{"Q1575556":{"pageid":1586296,"ns":120,"title":"Item:Q1575556","lastrevid":70742556,"modified":"2026-04-13T16:27:06Z","type":"item","id":"Q1575556","labels":{"en":{"language":"en","value":"On the competitiveness of the move-to-front rule"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1493364"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$F3F7E29A-61A3-4BB0-9889-FC3A5D72F0BE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"742a231771a452cc0e0a0c1980f14819332ecd66","datavalue":{"value":{"text":"On the competitiveness of the move-to-front rule","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1575556$1FCEDE6E-316F-4FEF-AD09-D93F801DE3F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e29543c249ad1cc370ce955f21ba574fa3c5321c","datavalue":{"value":"0947.68166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$4C33DFCD-5B63-4F60-A15B-61CD465B6004","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25b703a831365363fd229122909c3d64bf236031","datavalue":{"value":"10.1016/S0304-3975(98)00264-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$10D758F4-B53E-47FA-AFD9-58764FED6D00","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e80403a0d8bc147e9e8fa927279f80a0df3552c","datavalue":{"value":{"entity-type":"item","numeric-id":308945,"id":"Q308945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$83BD8FA1-5D98-4F59-8DE9-366606C84B58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d333238169a900ce8d269afb6a02b7dc62a8f79d","datavalue":{"value":{"entity-type":"item","numeric-id":390912,"id":"Q390912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$6EC67438-F028-403B-9815-866CFF5BB9A1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$AB9CB247-4BDD-4106-9868-CD28637D9C69","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3a497233c3b9babc42d370358782cbff338a7a1","datavalue":{"value":{"time":"+2000-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1575556$E60C4555-4509-4524-B4D2-6443BF6C7D45","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1dbc68bf826aba3406fe0203fde31a62ace77af1","datavalue":{"value":"We consider the list access problem and show that one questionable assumption in the original cost model presented by \\textit{D. D. Sleator} and {R. E. Tarjan} [Amortized efficiency of list update and paging rules, Comm. ACM 28, No.~2, 202--208 (1985)] and subsequent literature allowed for several competitiveness results of the Move-To-Front rule (MTF). We present an off-line algorithm for the list access problem and prove that, under a more realistic cost model, no on-line algorithm can be \\(c\\)-competitive for any constant \\(c\\), MTF included.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575556$5F7A61A7-AC4C-463C-8EF2-38222D91CEDD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$3910553F-4B17-42F5-8BD9-1599EBD4CA1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$0C1D6DC5-DA1C-4987-8C5A-2131FB377894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$FDBDCB7B-DE8B-47B3-90A6-ED5C93756AA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a515d78655aca1b4f21db68cee14dc6ade464a19","datavalue":{"value":"1493364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$CBD29CCC-E90A-43A4-91E2-DD0FD668188F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20a098d667eb6cb6aa4a6a4fd585b497a7de3628","datavalue":{"value":"competitive analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575556$7E16D6CA-429D-4BF3-8B76-F30914E34FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be09917c8b117d2a659118ad2b48f63fb5690a50","datavalue":{"value":"on-line algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575556$5047067F-F789-42E3-85C3-4BC29DC5B860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25083771907742b9d76905195897a3c14f4069a7","datavalue":{"value":"list update problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575556$75E668AB-4AEE-4FEC-AE58-EBF821E58D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"426fa8887e47a2044f48ee3e06fd3d2f043d33e8","datavalue":{"value":"move-to-front rule","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575556$62ED8992-5AAA-4AC3-948D-7877D1C64883","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$D55ED7B3-41D3-4C5B-B556-693602BBEC76","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d964e4150ed7404ae537884a9cb9260b72396203","datavalue":{"value":"Q61734812","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575556$81C5B12B-AA76-4762-9A3A-C927193D480F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb16a78ff93f36258225aedcb2b8c7879935c8d4","datavalue":{"value":{"entity-type":"item","numeric-id":1312184,"id":"Q1312184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$D550E40E-3A79-4301-AF86-EC784F740E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f490329910b943c82f94bbad02d317b0e3d9c94","datavalue":{"value":{"entity-type":"item","numeric-id":1892219,"id":"Q1892219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$15E4ABD5-4E79-4642-BAA2-05BF78C124F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5a298410dafe6ff6fee8bee1e7cdc50dda0b70e","datavalue":{"value":{"entity-type":"item","numeric-id":4302787,"id":"Q4302787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$F3038E46-063A-4D96-9BB8-8E299E1D0401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b58e0b24a4addc870729f84b5ddfde124bb2a2","datavalue":{"value":{"entity-type":"item","numeric-id":3988829,"id":"Q3988829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$7081FD11-E910-4491-897C-87EE17C53A78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72147d0a67b83d142284d352d91bed201180bd8a","datavalue":{"value":{"entity-type":"item","numeric-id":1329151,"id":"Q1329151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$3EF462CB-8781-4EAF-B114-510B3B7618AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c381eed78d67ce2ecf20aa8ac6c2ee170253045","datavalue":{"value":{"entity-type":"item","numeric-id":3911408,"id":"Q3911408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$5DE88D0F-3361-4E08-BB6D-8B9523DD25B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0861a0bd1f16697f7eafe0b87c72c10994f63c88","datavalue":{"value":{"entity-type":"item","numeric-id":1178243,"id":"Q1178243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$43E4D667-EC30-405D-BD4F-E44B39EDC40E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbfb9c6046c24a9de782722f95d05121b0107b5c","datavalue":{"value":{"entity-type":"item","numeric-id":4887013,"id":"Q4887013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$F2911DA6-A901-4D7E-B2DB-C1BAB07C5615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9ff78f4737a19da54a9c905e074e24403a88573","datavalue":{"value":{"entity-type":"item","numeric-id":4875207,"id":"Q4875207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$FC18502A-4B8E-4274-B36D-677A6A7DCAE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc1353f49cc1c764787cb8870644f418d80f2722","datavalue":{"value":{"entity-type":"item","numeric-id":3485852,"id":"Q3485852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$0FB1FCA4-7966-40E7-AAB1-B91967E36B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ccf02e26f49fc8408e9d4ed2f5a9c68fce2edfe","datavalue":{"value":{"entity-type":"item","numeric-id":1312185,"id":"Q1312185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$E8184AEA-0248-4A65-8A22-D1AB1CCF98AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2708e882937281b237ad6578d98e4eb2b386f2","datavalue":{"value":{"entity-type":"item","numeric-id":4079040,"id":"Q4079040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$35AE7256-61D4-40BD-BCE8-9036D4F8074C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"290d6d32723bc8a56ee307cdba6d7e3f8517e07f","datavalue":{"value":{"entity-type":"item","numeric-id":4231924,"id":"Q4231924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575556$A3B9E40B-FAB3-4D89-9C84-D580C68AD3F0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ccdc473e75c6e9421107505bd1f47ae93b77943","datavalue":{"value":{"entity-type":"item","numeric-id":3415956,"id":"Q3415956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"548492f886deab8aea8fb3dbf4f4b5773f4dcca3","datavalue":{"value":{"amount":"+0.8414230346679688","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1575556$BE78D9A6-A670-4789-9D90-B7D406A087ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b05f72e2afc7aa5ee73af018cd1cb8182f7bf1b","datavalue":{"value":{"entity-type":"item","numeric-id":5957574,"id":"Q5957574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3611789415c1e9d67ebcb2a4a5a43bca3e3b70e1","datavalue":{"value":{"amount":"+0.821405291557312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1575556$4C0C2165-9B33-46A5-8250-E5FA75EC19F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a151aa613b44bf14aee11a876f255ece384ec3c","datavalue":{"value":{"entity-type":"item","numeric-id":1178243,"id":"Q1178243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3480cde9ba753cb8acb1cc74c5bc9dd3f7cd8b52","datavalue":{"value":{"amount":"+0.8204551339149475","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1575556$C026D050-2D07-4D68-94F4-AF345F3A767A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the competitiveness of the move-to-front rule","badges":[]}}}}}