{"entities":{"Q1111472":{"pageid":1122221,"ns":120,"title":"Item:Q1111472","lastrevid":42884645,"modified":"2025-07-15T17:18:39Z","type":"item","id":"Q1111472","labels":{"en":{"language":"en","value":"Online variable-sized bin packing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4074824"}},"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":"Q1111472$EB5EA320-32EE-4B4C-81AC-1DEDC5E42CDA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"79daf57167fdb60c8433588de1cd41ac3759f544","datavalue":{"value":{"text":"Online variable-sized bin packing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111472$9DB7C290-0FEA-4279-B530-E480A0132248","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"735d54dd1274fffc0c9263a79c8214ec9e828cdf","datavalue":{"value":"0657.90080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$D88EDDF3-092B-4463-875F-C9BA4DF850A7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e58f31beaeea53b797c6730081b94a700b3b2f5","datavalue":{"value":"10.1016/0166-218X(88)90089-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$90CE5504-E17A-42FF-B37E-195CA914CF3C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"240c74fe2f8cca1d55a9e9ba399c9ff3620eacfc","datavalue":{"value":{"entity-type":"item","numeric-id":1111471,"id":"Q1111471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$ACDCAA86-7729-4627-A802-EEBF94398109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d288423df0deba1f237a49670693efc500bb8d57","datavalue":{"value":{"entity-type":"item","numeric-id":293396,"id":"Q293396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$E9914D5A-9A2B-4331-9135-9D315762406C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$33FAE9BC-966D-495F-862E-3FFF52C591E1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1111472$65EC122E-7846-42D9-85A1-588479847747","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2dd2b12765e2d73ec25ef8ad3c922c770a8f234","datavalue":{"value":"The classical bin packing problem is one of the best-known and most widely studied problems of combinatorial optimization. Efficient offline approximation algorithms have recently been designed and analyzed for the more general and realistic model in which bins of differing capacities are allowed by \\textit{D. K. Friesen} and \\textit{M. A. Langston} [SIAM J. Comput. 15, 222-230 (1986; Zbl 0589.68036)]. In this paper, we consider fast online algorithms for this challenging model. Selecting either the smallest or the largest available bin size to begin a new bin as pieces arrive turns out to yield a tight worst-case ratio of 2. We devise a slightly more complicated scheme that uses the largest available bin size for small pieces, and selects bin sizes for large pieces based on a user- specified fill factor \\(f\\geq 1/2\\), and prove that this strategy guarantees a worst-case bound not exceeding \\(1.5+f/2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111472$FB218A00-9B1C-4C75-B2D5-A8EA6F8CEF1B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$417FE855-2331-447D-87AB-FE1E481EE585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$F755387C-9A3A-4FF9-AC55-BCD9C3777AF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$0E260EA0-2C83-4AAF-A680-0B630891D7FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"954b07e5c6a233a2883aa369f160acdf883e580c","datavalue":{"value":"4074824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$CD09F6B0-81D6-4D10-BA6B-C4A8973C9C04","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ad2d23c1ed42bcf5e3bd1754605a5b060ca641","datavalue":{"value":"bin packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111472$8E56017E-43D1-4825-99D6-3D3BB5AEB648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1f57b05e1a2187ec4cd8864886ccd7f9c26a582","datavalue":{"value":"offline approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111472$3B79B50F-6701-4B36-AF73-AB7A1DFBDBCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0fca5ac8cddc8f74e7908fc7842929c55342241","datavalue":{"value":"online algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111472$59E6B272-0262-47BA-ABF9-91E3B558FC64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8344bbd8932c1dede81e2529ea78048ffeeb34bb","datavalue":{"value":"worst- case ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111472$09B5D5DF-9090-4292-82E5-92242F4F484E","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":"Q1111472$FD184DF7-10AC-4E09-80F5-88DAD1A9B94C","rank":"normal"}],"P223":[{"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":"Q1111472$EE846B8A-EAC2-4739-A343-82D6616764C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db208eea11dd27eab0df5d9b6966908c30b3cfb0","datavalue":{"value":{"entity-type":"item","numeric-id":795502,"id":"Q795502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$C830C6D2-002D-47B0-9DC2-5ED3DF16C7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93771cad22a629fe4bfc6961624a48bc9abcc357","datavalue":{"value":{"entity-type":"item","numeric-id":3718155,"id":"Q3718155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$BFAA3C10-9EC2-4D7D-AE66-4D6836271BCE","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":"Q1111472$1ED16974-4139-47CF-983C-3687B629ABBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b8e87d4a721feb93a36727cfd71d12911830dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1845315,"id":"Q1845315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$2D991052-5B5F-4F44-AF8C-A58E6A2ECF73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"769dac7a67dfc7875975b2be22cc73b5b5823d2f","datavalue":{"value":{"entity-type":"item","numeric-id":3754441,"id":"Q3754441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$62398EB7-ED71-4A3F-8A93-D7D32107DCD2","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":"Q1111472$09FE0ACC-B666-4F78-BFD6-39C34B3E7613","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":"Q1111472$798D2E05-9678-4FC0-8FD5-12A13B2A699F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea64a2613533992f48d2033e44b83e5aced52177","datavalue":{"value":{"entity-type":"item","numeric-id":3755240,"id":"Q3755240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$39E01895-132A-4A02-8D6A-889621DEAC18","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":"Q1111472$BD30ED59-4038-450D-ACFB-2C02E44BE503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a4c6e73fd0240bebe5fafe880bb43b56c576eda","datavalue":{"value":{"entity-type":"item","numeric-id":3873560,"id":"Q3873560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111472$044D15D5-C693-45D6-BDF7-509A12CF269A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a5bad79e21bd031c4d4b84101dd057355d462e54","datavalue":{"value":"https://doi.org/10.1016/0166-218x(88)90089-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111472$5AE14658-A23A-4098-AD38-2776B933F8CE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"390f2032db787f61caf6428920880aa941273fb1","datavalue":{"value":"W2019755210","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111472$35FC4DCE-0341-4E2A-83B2-B078AEEB968F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d1ec3feb7b1a2848705a7bc4b6d68e73a3ce25f","datavalue":{"value":{"entity-type":"item","numeric-id":429693,"id":"Q429693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f15a574bdb8a63893938a1668714369ce0c66ee","datavalue":{"value":{"amount":"+0.94085586","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":"Q1111472$70FB8630-3947-4999-BD0A-C6B211B873D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df29e631bebc23e7ddab2b2a9beab259836d9fab","datavalue":{"value":{"entity-type":"item","numeric-id":582083,"id":"Q582083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb9f398f7ab4be1acdb89cf4614dbbb99fac9a65","datavalue":{"value":{"amount":"+0.9372967","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":"Q1111472$9F1D0201-BAEF-423D-9D4E-6984FFD6D15D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e99862577b6be1592019a977d742c9484dfb9f4","datavalue":{"value":{"entity-type":"item","numeric-id":2001455,"id":"Q2001455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee287913a4b77b91991dd2d6662cffdc72e5d933","datavalue":{"value":{"amount":"+0.9358449","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":"Q1111472$DAE34EEB-4021-43BC-9856-F6476615139F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7de506b841b60b39e3cc8efb667f26b9f9de5665","datavalue":{"value":{"entity-type":"item","numeric-id":674434,"id":"Q674434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c09fd4332914ea2d8c4af1f5677b29bd3316b1f9","datavalue":{"value":{"amount":"+0.9330803","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":"Q1111472$A4C35B3A-1447-47FA-B68F-54F0F0E474D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e535d05c2216dcfbebd39bf4b840d4984e5b7d0","datavalue":{"value":{"entity-type":"item","numeric-id":5896936,"id":"Q5896936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21d10d24088cf3cfe8c6d5a19572c2c9cee1f651","datavalue":{"value":{"amount":"+0.9257123","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":"Q1111472$515B8777-5545-4183-986F-1050ACAAF1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cb57db1d9046e15228cd9d300a06b9d09cf1057","datavalue":{"value":{"entity-type":"item","numeric-id":3575450,"id":"Q3575450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21d10d24088cf3cfe8c6d5a19572c2c9cee1f651","datavalue":{"value":{"amount":"+0.9257123","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":"Q1111472$0D64DFF4-07BE-41BB-A75F-79ACA1B39662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbe89d52b3fb6cc9fc92d47782bf3e0127923d73","datavalue":{"value":{"entity-type":"item","numeric-id":4382124,"id":"Q4382124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"171eb01922402044acb87d4a9515fe7ab362969d","datavalue":{"value":{"amount":"+0.9237526","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":"Q1111472$831BB8FF-35A3-41BD-8D06-07C8FF8160FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13332937a9f1824c889eeeb23aa315b6f99ff344","datavalue":{"value":{"entity-type":"item","numeric-id":5755519,"id":"Q5755519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b94963afcc2c197f01591a435ef8dcd229e5859","datavalue":{"value":{"amount":"+0.9226746","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":"Q1111472$72B65543-FAD1-48A7-9D72-AADBD8D4CBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88cadb62792261e6e47983b59012d642e19f428b","datavalue":{"value":{"entity-type":"item","numeric-id":4535798,"id":"Q4535798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f93997a6e45ef6280f79756ed130b97ccf7aef7c","datavalue":{"value":{"amount":"+0.92159176","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":"Q1111472$64CB09B0-82D1-47A5-B7EE-E9C419078DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f5f475e72cb2bfc22a3dd70d09a2caa7f3f2310","datavalue":{"value":{"entity-type":"item","numeric-id":3455545,"id":"Q3455545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f93997a6e45ef6280f79756ed130b97ccf7aef7c","datavalue":{"value":{"amount":"+0.92159176","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":"Q1111472$30E2C9AB-2E2A-4E80-8639-1184CA8D7B00","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111472","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111472"}}}}}