{"entities":{"Q1591548":{"pageid":1602288,"ns":120,"title":"Item:Q1591548","lastrevid":67937223,"modified":"2026-04-12T20:20:59Z","type":"item","id":"Q1591548","labels":{"en":{"language":"en","value":"Linear time-approximation algorithms for bin packing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1547202"}},"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":"Q1591548$7F896B50-E31C-44BA-A89A-941686709312","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c244443c08233401cacdd0730e48839ef3e1adf0","datavalue":{"value":{"text":"Linear time-approximation algorithms for bin packing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1591548$A1CC506F-C3C0-4787-AC7C-A77D12BBDF42","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2585002c083b7bbe0f6479122c861fa99a3cf9e8","datavalue":{"value":"0960.90096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1591548$25EB9AB7-1FA5-430A-9E72-3651DC5E6C3B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f3f5b327cc502a4872a44e347210445a2bb8a2e","datavalue":{"value":"10.1016/S0167-6377(99)00077-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1591548$09E6A7E4-9581-4D98-8855-467C620C8854","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ca85145c5bcf26b9d6b48940983710606ab54cb","datavalue":{"value":{"entity-type":"item","numeric-id":1581051,"id":"Q1581051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$62300FAC-8D74-42F3-ADF6-9FFC62A52662","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$B62FE60B-DDD4-42F4-A186-2C9919A2ABE5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1aa702799bba8332feed35d198b58d4c2e376e02","datavalue":{"value":{"time":"+2001-05-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1591548$FB98E27E-EF92-415A-AB52-652F4AF57D8D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"afc3e82caf6b63fc63c308c1b0b4e9d030934a19","datavalue":{"value":"\\textit{D. Simchi-Levi} [Naval Res. Logist. 41, 579-585 (1994; Zbl 0809.90111)] proved the famous bin packing algorithms FF and BF have an absolute worst-case ratio of no more than \\({7\\over 4}\\), and FFD and BFD have an absolute worst-case ratio of \\({3\\over 2}\\), respectively. These algorithms run in time \\(O(n\\log n)\\). In this paper, we provide a linear time constant space (number of bins kept during the execution of the algorithm is constant) off-line approximation algorithms with absolute worst-case ratio \\({3\\over 2}\\). This result is best possible unless \\(P=NP\\). Furthermore, we present a linear time constant space on-line algorithm and prove that the absolute worst-case ratio is \\({7\\over 4}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1591548$007CA9BB-A554-4EB8-BD88-12B8CDAE13D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1591548$0439C790-1E4C-486C-A8EE-79B954D36B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1591548$062C24F1-028D-4087-A7BD-BE5BED277751","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e470aca190e0b6679466267581e2aa5a2de0f1f9","datavalue":{"value":"1547202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1591548$B7688B83-CCF6-4B44-870F-40561912C315","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ad2d23c1ed42bcf5e3bd1754605a5b060ca641","datavalue":{"value":"bin packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1591548$48671D5E-E15D-4166-84E5-9D8B218F5259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f19b657d4fd6cdccb28395320216f8ab14bc4018","datavalue":{"value":"absolute worst-case ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1591548$CAAE7AAA-42F1-40F6-944B-9D318D852A0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1591548$8E767E12-3562-48AE-9DAB-900D1FF59485","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":"Q1591548$56758CB3-4414-4BF0-A7B0-1046189B6D02","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$EAA3271C-5D82-4987-8804-CE5F3A87B308","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":"Q1591548$DE8DC74A-37F2-4084-9CB4-E4E3E8B8C4F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$0E9BF25F-FFE2-474D-AAD9-9F6F9FB6FBF7","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":"Q1591548$BEA0576C-4794-4BA3-B86E-F756F9EEC1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc1e695141c6883bdb69438c53b3cc2b5dc75f3c","datavalue":{"value":{"entity-type":"item","numeric-id":3766848,"id":"Q3766848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$C0F6E459-69E6-4525-8D9F-1EFEBF4AAE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8d0b5c7555ce32ecb083248acce4ff79eef6d79","datavalue":{"value":{"entity-type":"item","numeric-id":1062626,"id":"Q1062626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$9FBAD5DA-806D-41C2-AED7-154C7240C1F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df11f1fb23c64fb2173b02a4f7530e467ba1ca8b","datavalue":{"value":{"entity-type":"item","numeric-id":4732116,"id":"Q4732116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$CA5E7753-5EAB-4831-99D7-447533EE8B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"169c9957a2115422233fe80a5d5866c1d19f84f3","datavalue":{"value":{"entity-type":"item","numeric-id":4290987,"id":"Q4290987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1591548$3FD1AF44-D7A6-49B3-BA40-06CE04356F3A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f64a8d5d677e9ef8d5e90fb88cf6fd669fbaff10","datavalue":{"value":{"entity-type":"item","numeric-id":1062626,"id":"Q1062626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6144ccd04af9cd6c8198e7c8cf96b38154e8200e","datavalue":{"value":{"amount":"+0.9641307","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":"Q1591548$A51FDE5D-C48C-445D-AA46-62CC21A85BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"622db6f73e20678d0a51ca6f21fc055a7f547a09","datavalue":{"value":{"entity-type":"item","numeric-id":1034628,"id":"Q1034628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"531cdafece65810856c642dba741273a1fc85416","datavalue":{"value":{"amount":"+0.9404049","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":"Q1591548$32DFB753-D7BC-469B-8894-6070BD2CE10D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e031d0f7dc8576b37c50b19ddc15fabdbac53b8c","datavalue":{"value":{"entity-type":"item","numeric-id":2768352,"id":"Q2768352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39a5adc2be7a1c80857da77b87ed84cc197fb73e","datavalue":{"value":{"amount":"+0.9341613","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":"Q1591548$E600D23C-2289-444B-BFB4-A3BC0520E261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6470956f9dce8fa52b78b4b09dc31c3f910b9ca","datavalue":{"value":{"entity-type":"item","numeric-id":880529,"id":"Q880529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39a5adc2be7a1c80857da77b87ed84cc197fb73e","datavalue":{"value":{"amount":"+0.9341613","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":"Q1591548$891D358C-0C1F-4AE9-B59B-0F225286B3B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"632bbf5f0b7172a2d30a50a09efc13280059dfaf","datavalue":{"value":{"entity-type":"item","numeric-id":4732116,"id":"Q4732116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e8746c4eb15e4e778807948da13473a1224b0c3","datavalue":{"value":{"amount":"+0.93327177","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":"Q1591548$36FC3BE6-46C3-47EC-980F-3FE3AB003D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c357b1c208d837dce19b95b6d6ff909af048ad9b","datavalue":{"value":{"entity-type":"item","numeric-id":1679514,"id":"Q1679514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edfc58eeb84f5c9e469d2311cb04e0747f368f6a","datavalue":{"value":{"amount":"+0.9302741","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":"Q1591548$718590F1-EF81-4B44-BFD8-B302D35E2D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"601810f3eb700d4f290276c0c2c661d4e4f9f8f9","datavalue":{"value":{"entity-type":"item","numeric-id":1975969,"id":"Q1975969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d452a140d1f42b4cca57860e610b1891cf745be","datavalue":{"value":{"amount":"+0.92465407","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":"Q1591548$8C9A580C-2503-4811-B04F-7ECD71DF3068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69fc1d675ce2daa9b0a7960cf4dbcf860c751738","datavalue":{"value":{"entity-type":"item","numeric-id":3538741,"id":"Q3538741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5eb1c892c2a0163a21ce26a0f4f1f61c30ec34ad","datavalue":{"value":{"amount":"+0.92426777","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":"Q1591548$8BCD06D8-CF01-4AFA-AC39-F8CC206DDD7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db98a3cd17d6aa96dfc71f4c064e4ab796e22600","datavalue":{"value":{"entity-type":"item","numeric-id":3347319,"id":"Q3347319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65cf710bbcfb9f2b1106182e630619f66f38f810","datavalue":{"value":{"amount":"+0.916404","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":"Q1591548$4E865B92-01B1-4F7C-8A91-F52BCFA84C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ff296b02faf4d75897e915dff9c37f413e35426","datavalue":{"value":{"entity-type":"item","numeric-id":2897992,"id":"Q2897992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b74cc9e9472d57922086191b4d0d6e31d88273c1","datavalue":{"value":{"amount":"+0.91438735","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":"Q1591548$F38D78A7-92E9-494D-BFC6-C7D98C7297EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear time-approximation algorithms for bin packing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_time-approximation_algorithms_for_bin_packing"}}}}}