{"entities":{"Q40503":{"pageid":40559,"ns":120,"title":"Item:Q40503","lastrevid":105427817,"modified":"2026-10-09T10:08:27Z","type":"item","id":"Q40503","labels":{"en":{"language":"en","value":"List Update Algorithms"}},"descriptions":{"en":{"language":"en","value":"AFP entry List_Update"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"eeddb5c0c9ca6a2b366b08b264413f94e8ec32a0","datavalue":{"value":"28789","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40503$EE061A63-2CEA-4A18-A595-8AB3C82F3801","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$D23687F6-2114-4F96-9D0D-0EFBBAA4F74C","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"2a48eaa42b74c4a3784950141feee8d8c98c78d1","datavalue":{"value":"https://www.isa-afp.org/entries/List_Update.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40503$9BCED822-28DD-42B6-B875-F0B3C8876F8C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40503$2066B3B6-BC18-40F8-9DCF-6AA6087EC394","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cb15924b3f11a91ed3d52d01ae18199742cf1a39","datavalue":{"value":{"entity-type":"item","numeric-id":22078,"id":"Q22078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$FADCEEC7-3970-4046-B33B-0FDF94C0EBAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"144f0221487b5ba035abaca0f440960a9e47efeb","datavalue":{"value":{"entity-type":"item","numeric-id":27113,"id":"Q27113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$CE683D97-907F-4831-B23C-D5CF376ADA1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$F2875076-9D53-4DED-9406-209022986116","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec2d573ef99b05bb91d675b04832ad031374bae2","datavalue":{"value":"https://isa-afp.org/entries/List_Update.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40503$E253D730-4211-42CE-97C2-7F25BB9EC3AD","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"02a0004599e94931eff0c15dfad08c7ac7fe5d28","datavalue":{"value":"Maximilian P. L. Haslbeck","type":"string"},"datatype":"string"},"type":"statement","id":"Q40503$06EB9FC6-E0E3-4FD2-85E0-A590D51A9C63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"78083bbf5b06a4f292e9e00ee445948e4fa51db5","datavalue":{"value":"Tobias Nipkow","type":"string"},"datatype":"string"},"type":"statement","id":"Q40503$5223AC1A-F8EC-4936-9ED5-5E8A5BF2B64B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"68a4916d3a05ce3952e80671e1448604486833f5","datavalue":{"value":"These theories formalize the quantitative analysis of a number of classical algorithms for the list update problem: 2-competitiveness of move-to-front, the lower bound of 2 for the competitiveness of deterministic list update algorithms and 1.6-competitiveness of the randomized COMB algorithm, the best randomized list update algorithm known to date. The material is based on the first two chapters of Online Computation and Competitive Analysis by Borodin and El-Yaniv. For an informal description see the FSTTCS 2016 publication Verified Analysis of List Update Algorithms by Haslbeck and Nipkow.","type":"string"},"datatype":"string"},"type":"statement","id":"Q40503$B15251F9-CF86-4788-9207-3EAB6AFF6BE5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a64c66f84ef3d614c129d9701b7e0cb0d4d62295","datavalue":{"value":{"entity-type":"item","numeric-id":4223058,"id":"Q4223058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$06401248-A3E0-4144-8211-8406BF1AB86B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b769aba687587233fb5a63cffdf0c7f71a8288b","datavalue":{"value":{"entity-type":"item","numeric-id":4636599,"id":"Q4636599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$23106E81-130B-430D-8785-CEF8B11C4F8D","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0b5465b6a0d9e05645cdb7168eee1aaf7eb2845","datavalue":{"value":{"entity-type":"item","numeric-id":7361518,"id":"Q7361518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$658A5791-17BD-44A9-A7AD-E7A4C7D7C5C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"a0e462408f240420e2b3f4dd5e025dcac9e4a9cd","datavalue":{"value":{"entity-type":"item","numeric-id":7361044,"id":"Q7361044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$42C70705-59FF-4B06-8288-C8992E00F25E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cccc2e9774146717f2e9840d2775c6348713b9b9","datavalue":{"value":{"time":"+2016-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q40503$72206C20-824D-4A43-9968-A7141510A467","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e6e34ec5f405a28b5c3a1be684a4e2d9dbeefd2f","datavalue":{"value":{"text":"Analysis of List Update Algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q40503$0EA766A3-DB1B-4AFD-9C0A-7FBD89094325","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$1E188489-89D5-4EA6-B45B-E78698D42F9C","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"c8b9ba5ce1235e56c9dd453169f601676e182576","datavalue":{"value":{"entity-type":"item","numeric-id":7360779,"id":"Q7360779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40503$AC765F33-E256-42FA-87BD-88D7F3BCF461","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"List Update Algorithms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/List_Update_Algorithms"}}}}}