{"entities":{"Q1100912":{"pageid":1111664,"ns":120,"title":"Item:Q1100912","lastrevid":49154029,"modified":"2026-01-06T16:37:22Z","type":"item","id":"Q1100912","labels":{"en":{"language":"en","value":"The average-case analysis of some on-line algorithms for bin packing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4045180"}},"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":"Q1100912$54200F5E-A009-4523-A359-696259E20253","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9066ae1db2e56bca551ea31741ef7b717840d18","datavalue":{"value":{"text":"The average-case analysis of some on-line algorithms for bin packing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1100912$D84375E1-8BA4-426B-9D10-A4E5BEA9717D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b8d1b684bd1664641377747051c4e686c33a5d2b","datavalue":{"value":"0641.68096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$FB448680-4A0F-45B0-A028-B52260D38D7A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72bd90406fe14fe88a4bcb9e5029762a6380ab75","datavalue":{"value":"10.1007/BF02579171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$F7D90BC5-C88D-4C0B-B455-69D5339DAAC7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$C00D357F-B9B4-4164-A9B3-FC6ED547164A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1100912$62472726-D1F2-47E3-AF17-3373E80D9682","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab07772e30b54474294f58b6323570d741cd05fe","datavalue":{"value":"In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0,1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100912$EF61FE35-C176-4A2C-81E9-16A244735E81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$4150DF2A-58C3-43C4-BCA0-85E19EDA5CC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$FDB7ADA6-0698-4056-9FDB-E25855EFB0C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$B4D7F812-5491-47E1-AE7E-82CD381EAC53","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fc19d834b473bec73b014880bd2d2a9f38ef563a","datavalue":{"value":"4045180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$5B0F283D-BD58-425B-9AF2-B544A59EEC00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be09917c8b117d2a659118ad2b48f63fb5690a50","datavalue":{"value":"on-line algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100912$1143943F-2668-4EEC-B684-6A7BFB9AD66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ad2d23c1ed42bcf5e3bd1754605a5b060ca641","datavalue":{"value":"bin packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100912$416874BA-13B7-482A-B440-36F98B02D2E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3893f33a289a9d92f4b5c4918fe37ca345f5a802","datavalue":{"value":"up-right matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1100912$7921555F-3523-4B09-89D3-59D1F277A19F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81778509c7c34d1a374c80a7a64e0dd6e1cd7f8","datavalue":{"value":{"entity-type":"item","numeric-id":701710,"id":"Q701710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$B19CBED0-1CB8-4006-A7F8-A0401DC4EDA5","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":"Q1100912$BC20B67B-BFD3-4143-B7A3-9ED1AF159753","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"00963eb641e0e6dcd560c562d8508474fc3a1b4d","datavalue":{"value":{"entity-type":"item","numeric-id":1056968,"id":"Q1056968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$A8F952CA-CD28-4C17-8836-0D439C18115D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"771397537c548c7aba46f71f4dc817d9120e0b77","datavalue":{"value":{"entity-type":"item","numeric-id":3347319,"id":"Q3347319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$C133798D-6AB8-4209-81D0-27E8D8DC0AD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea4f62ba18f9284fe3e8b963487ec10490dfe079","datavalue":{"value":{"entity-type":"item","numeric-id":3893332,"id":"Q3893332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$EC3D99E1-400C-4694-B623-87F2F2725EAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db9a4f058bbac6c3fad57747273899a5bbfb3336","datavalue":{"value":{"entity-type":"item","numeric-id":3938275,"id":"Q3938275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$4042B93D-1FDB-49E6-B678-312D496DEAD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db748639fa4ae399773cbacdf7d1a894faee7de8","datavalue":{"value":{"entity-type":"item","numeric-id":1164429,"id":"Q1164429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$8C0E6E44-54CE-4193-9102-5AB147637CA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02ded4165b74ce94271724dc415f092ed63ab599","datavalue":{"value":{"entity-type":"item","numeric-id":1149248,"id":"Q1149248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$35DE4967-A924-4DD3-89AF-4A696ECB7271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a84ca05055b81b1d4477c12adf902e5f849b5539","datavalue":{"value":{"entity-type":"item","numeric-id":4051589,"id":"Q4051589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$72C6A348-47DC-4168-BFB8-499D9F415DB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81c5522381397257122f80a2e9449cb518db7c64","datavalue":{"value":{"entity-type":"item","numeric-id":3347792,"id":"Q3347792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$C7248FAC-0ED1-4D0D-BE10-E154DFF06674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebb9803a32cf800cb238e777d474df3c9601d497","datavalue":{"value":{"entity-type":"item","numeric-id":1262767,"id":"Q1262767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$AF5511B3-CF9C-416D-BDC1-0B93FF31F12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17fe71bc56d36be0b7641f26e1f36d0dfc200b98","datavalue":{"value":{"entity-type":"item","numeric-id":1144944,"id":"Q1144944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1100912$465B5032-9180-448E-8348-F7D761B925B0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d5f829a57b7849e8fa5dc62b39099eec54d647e2","datavalue":{"value":"https://doi.org/10.1007/bf02579171","type":"string"},"datatype":"url"},"type":"statement","id":"Q1100912$5410F9C9-51B0-4288-AFC0-EE1832F35CC3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b4f742375f35a31d52cd5c3aba1509608fdd260a","datavalue":{"value":"W2009931551","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1100912$FDE267C2-177F-49A5-9D35-64F1EE85C3F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d401f31b88d97a9f9aaab743a5b4ece810c7865f","datavalue":{"value":{"entity-type":"item","numeric-id":4712660,"id":"Q4712660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"882a911385d16b9e04652f433d19946ae0240e93","datavalue":{"value":{"amount":"+0.8977147936820984","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":"Q1100912$6BA28E98-371F-4DE6-8BFF-D3A32FB07106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"babd77007b40a465994dcca531f73db6d80e8e6a","datavalue":{"value":{"entity-type":"item","numeric-id":4487093,"id":"Q4487093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25fc208dcfcc9b3de2ae86008a3df9ae26045595","datavalue":{"value":{"amount":"+0.8936403393745422","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":"Q1100912$A74A4416-51CC-4DE7-931F-6A1B219AEF8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d34481ea1da72ed0a352e4bcdf3b399e53dca11f","datavalue":{"value":{"entity-type":"item","numeric-id":4875207,"id":"Q4875207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28273ee05c4216144a725e60d13da3705d45ca1d","datavalue":{"value":{"amount":"+0.8786489367485046","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":"Q1100912$16B9E11B-EF90-45E0-BD80-073006777E46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"492236894bef0575857cbda1e0a968c5a3c8a5a6","datavalue":{"value":{"entity-type":"item","numeric-id":1065544,"id":"Q1065544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28273ee05c4216144a725e60d13da3705d45ca1d","datavalue":{"value":{"amount":"+0.8786489367485046","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":"Q1100912$2A39F2F4-5414-411F-BF47-B9551DD8E711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"408971ef6dd9323fbe5e1894e34a8e99a4f49ef0","datavalue":{"value":{"entity-type":"item","numeric-id":1825655,"id":"Q1825655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75ac41f0ad5dbf9b8b230e5ebb2324d467791b1f","datavalue":{"value":{"amount":"+0.8749635815620422","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":"Q1100912$CC616F8F-1951-4334-BD84-F1BA15DFAB14","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1100912","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1100912"}}}}}