{"entities":{"Q685486":{"pageid":687335,"ns":120,"title":"Item:Q685486","lastrevid":42641202,"modified":"2025-07-07T14:52:54Z","type":"item","id":"Q685486","labels":{"en":{"language":"en","value":"A lower bound for randomized list update algorithms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417397"}},"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":"Q685486$53B9EFF7-E111-4470-9BD9-291702DB6492","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d43e93ccd16ccd9e1509dfbd3cbec2614bf9bdef","datavalue":{"value":{"text":"A lower bound for randomized list update algorithms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685486$6C211B6F-6073-4909-8D5E-DED106E20DE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f15544aca685abb35370c3e6c794bef2dad95285","datavalue":{"value":"0794.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685486$D51F143F-C2F1-4CDC-BEA6-3AA90E7A2676","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f761849c37ab8f4fe27c21378362878545af0311","datavalue":{"value":"10.1016/0020-0190(93)90150-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685486$086928A4-03EE-41EF-89F9-A320FDE1B41B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1fd7edc63f9120aaefdc7456217aaf7b6d54282","datavalue":{"value":{"entity-type":"item","numeric-id":685484,"id":"Q685484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685486$817400E8-2427-4CC5-BB25-15E02F0E6FC3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685486$9BADCBE3-BB36-4F32-B3C9-CB531A68ABCE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-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":"Q685486$13A4C296-6AB6-4BAC-827F-2C703930BDB7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e403c8c66faa9b5bf4c0a58d374151ec268eab4f","datavalue":{"value":"The author deals with randomized online algorithms for a static list update problem. As a main result it is shown that 1.5 competitiveness presents a lower bound for such algorithms, i.e., the expected cost of any sequence of requests is no more than 1.5 times the cost of an optimal off-line algorithm.   The original research is combined with an older result of \\textit{A. C. Yao} [Probabilistic computations: Towards a unified measure of complexity, Proc. 18th. Symp. on Foundation of Computer Science, 222-227 (1977)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q685486$A35DCF2D-293D-4034-879E-51FC2804B67F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685486$95C9E493-32C9-4633-805D-789F8C850890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685486$7CFF983C-49E2-414D-B1CE-49CBD063B4A2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"747f19338aa090366551bcf236227ff13f8122a5","datavalue":{"value":"417397","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685486$D4466096-F7ED-47B8-A24D-190849CFB4AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"354fdc9776836a5b32404d7f027f0d5a6b3a8008","datavalue":{"value":"list update algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q685486$74F2DD2E-5E3C-43B8-991E-E1D5D7CC05E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q685486$1EF28CF4-33A2-4B25-AC5F-198967FFA642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49eb4dac5aeb1a5fd4804122c81f369b6968def6","datavalue":{"value":"randomized algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q685486$8E0411AE-E7FC-4F6A-9EF8-9A7AEFBC20F4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685486$69CE32EF-5097-42EF-ACBE-C72EF864AE52","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":"Q685486$6DF191C6-A223-4CB5-9C04-3C150FDD40AE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d56559f55f5ea14a8703989d2eb0dec8dfd7e27","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90150-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q685486$82119DAC-611A-49AD-B5E5-425E837E497C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c7824b51fbef56f506e3a5456a41bfdf892cb73c","datavalue":{"value":"W2006254254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685486$6CF5EFD8-0703-40BC-A04A-358F157167E0","rank":"normal"}],"P223":[{"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":"Q685486$05DDC5A1-9A53-4424-9427-35F135DDD3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d724d1e211f4d52dd6da42555bb0a386e3166d48","datavalue":{"value":{"entity-type":"item","numeric-id":3138960,"id":"Q3138960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685486$A7BC1043-1E5B-4B03-AFCB-98FF8BF4B522","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffbfdfa65a5fba59a144364ad54a9ef5bf36488f","datavalue":{"value":{"entity-type":"item","numeric-id":1312185,"id":"Q1312185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7af77098ef32d3bbbeea63855bca019b8c6d2aa","datavalue":{"value":{"amount":"+0.9313799","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$79330871-49A5-4724-92CF-10B5C64F8CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd23f4f724858432bcaeabf219963c907ddf3783","datavalue":{"value":{"entity-type":"item","numeric-id":1277389,"id":"Q1277389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d61b27447ed1532d179aadca87ca5814f19cf3ec","datavalue":{"value":{"amount":"+0.9151597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$9D4CFBB2-2F4A-43CD-BB92-3C60CC83667F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb7b1f42ea1928a14319c5ae52ff91d0c4d554fd","datavalue":{"value":{"entity-type":"item","numeric-id":4388893,"id":"Q4388893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1738c316385db390027ab2bc58d3421c99c8061b","datavalue":{"value":{"amount":"+0.91339165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$887D9674-1894-46C3-A863-08D358EBF923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04ebcead04da3ac6601d519822b318acd44ff449","datavalue":{"value":{"entity-type":"item","numeric-id":4886073,"id":"Q4886073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1738c316385db390027ab2bc58d3421c99c8061b","datavalue":{"value":{"amount":"+0.91339165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$104E3491-7CD9-4FE7-98FB-0E89E99414A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"321d19c56c1eb4c93ffdec1bd2947a794c99909e","datavalue":{"value":{"entity-type":"item","numeric-id":2933662,"id":"Q2933662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fde677ea4c02081d12a243eea674473b3c8fbc6","datavalue":{"value":{"amount":"+0.90634555","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$84747A7E-F6B8-4A2B-AE73-07484397720B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8c30502a3ec235116d6131abf67dea89feef12e","datavalue":{"value":{"entity-type":"item","numeric-id":5958711,"id":"Q5958711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca098c79a7989be0a48db5cfaf3ee9d705284385","datavalue":{"value":{"amount":"+0.89964914","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$38CB312C-2506-4384-890E-5BD5BF5F7B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9e85e8f3d21cc83837597dc6c27f67affd10bf5","datavalue":{"value":{"entity-type":"item","numeric-id":826088,"id":"Q826088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56325f3e4cf41885f8abf524086632ca9ea1a8b4","datavalue":{"value":{"amount":"+0.88453376","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$96708E2D-2125-4F75-8892-8DC8C9F52F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c333b328e9a9f43971a5cdbaec1b33aa1ec1733e","datavalue":{"value":{"entity-type":"item","numeric-id":1350929,"id":"Q1350929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aae1245d9b0d683cf6604274952d8e22cb498097","datavalue":{"value":{"amount":"+0.8772931","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$9389377B-54CD-4858-9E08-047CF3E5F84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf66596a3de637d425dcebfa060509869c7142ac","datavalue":{"value":{"entity-type":"item","numeric-id":4542540,"id":"Q4542540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c2950c563e4d13ca538982c276dd936e409b9d6","datavalue":{"value":{"amount":"+0.870015","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$CF85AC19-DD8B-4C2A-9E53-693784530790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46092b20670b18adf19132557cc46799d896217b","datavalue":{"value":{"entity-type":"item","numeric-id":4645177,"id":"Q4645177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2f487ed18e510c70d24526888be59da69420ea3","datavalue":{"value":{"amount":"+0.8658382","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685486$EEEC394E-79A3-41B9-9739-DD4522B38746","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685486","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685486"}}}}}