{"entities":{"Q5958712":{"pageid":8135514,"ns":120,"title":"Item:Q5958712","lastrevid":47755804,"modified":"2026-01-02T14:55:35Z","type":"item","id":"Q5958712","labels":{"en":{"language":"en","value":"On-line bin-stretching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715757"}},"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":"Q5958712$0B1C004E-50CC-4B54-B09C-81018993EB83","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"be8cfbf634332c87d211f3a27aa46f699bd46c3d","datavalue":{"value":{"text":"On-line bin-stretching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958712$FDFDE2B2-80A6-4147-BED2-A68444625312","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"34f3b49ed55367072ca6862d0ea35bc215c757b4","datavalue":{"value":"0984.68195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958712$ED40F84B-E4CE-4577-811C-045948678AC3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5203a7f58f1b6003cb1c74818e462a12f2035de8","datavalue":{"value":"10.1016/S0304-3975(00)00258-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958712$E9ADAC17-6794-4BAA-87CC-A2B29AF3D92C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68814389157e3d8757e8eed17277cd2e82d90c5b","datavalue":{"value":{"entity-type":"item","numeric-id":526845,"id":"Q526845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$F36E9081-FDA8-4596-8FD9-A50F96447FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9f6b5d26f49366977cda1349aa1fe24902e4163","datavalue":{"value":{"entity-type":"item","numeric-id":375694,"id":"Q375694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$41B95BEA-6915-4066-8755-22158967E7FE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$4BCD6164-FA63-4190-B07C-86543F05130C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958712$74B77DB0-0371-4C65-A5E1-A007A69D9CD1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f112176a800471adcea372641fe494eb19d87c1","datavalue":{"value":"We are given a sequence of items that can be packed into \\(m\\) unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. In contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. We present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of \\(5/3\\) for any number \\(m\\) of bins. We then combine the two algorithms and design an algorithm whose stretching factor is \\(1.625\\) for any \\(m.\\) The analysis for the performance of this algorithm is tight. The best lower bound for any algorithm is \\(4/3\\) for any \\(m\\geqslant 2\\). We note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the value of the makespan (maximum load) is known in advance.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$58F420EE-CFA0-4611-8241-336A09F98767","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958712$CD8FC00D-9765-4966-A0CC-94C96F1412D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da2fa83ab5055241d43047d233782b01e5af2bbd","datavalue":{"value":"1715757","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958712$5780727F-0FA9-4CE9-A34D-8ED1A018030E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be09917c8b117d2a659118ad2b48f63fb5690a50","datavalue":{"value":"on-line algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$4C286821-6B3F-474C-9E6B-320ABC629D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$FAF915B2-1FA6-430A-B431-01DE6A5F30F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3059f9ec326756517524a5bcea156aeefc4b1e82","datavalue":{"value":"bin stretching","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$9803C7A7-A3CD-4964-BC3E-A8842630BD2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"680317bb7cb666013d85291c4be9842165075d1c","datavalue":{"value":"load balancing","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$D2B1B036-1454-42C7-BAB4-2EF4375B4694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$64E7D652-A93D-443C-80D1-D79E60771BE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"250707971bd9a23196cafda6a96d86b857c5daa6","datavalue":{"value":"bin-packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958712$EDE897B2-5895-4C55-A21F-3049E63E805E","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":"Q5958712$93DDA503-6A2F-4683-BDD9-2E53A6D55383","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b25194651134b5ff75934c650bd4bb6aa43e26e6","datavalue":{"value":{"entity-type":"item","numeric-id":4527046,"id":"Q4527046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$D3A66D99-B138-48CD-ADE8-1F5388BE2E2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2593d62c5ee82f57d17a663342c5ab8f36b63416","datavalue":{"value":{"entity-type":"item","numeric-id":5248533,"id":"Q5248533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$DC016047-0EB3-4EF1-9A23-5AB6C2FFDE85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2beb4871ca6daf7a18b37fb7b52ecc05761a3a","datavalue":{"value":{"entity-type":"item","numeric-id":3128891,"id":"Q3128891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$7F50252D-08D3-414C-8484-543033E1313A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ea15f4327bcce3b12251b0956fe888a7877e7e8","datavalue":{"value":{"entity-type":"item","numeric-id":4230343,"id":"Q4230343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$98DE02B9-E367-481B-8401-65544FAA0B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac34a02b34fc67558a4fc7e979d8b9fa2c98e409","datavalue":{"value":{"entity-type":"item","numeric-id":4652641,"id":"Q4652641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$BAAE8AB1-CA70-43F3-8D2C-86F13B21140D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4016d254f0b0b7c443ad645f96363a4ccdd3bb4e","datavalue":{"value":{"entity-type":"item","numeric-id":3125220,"id":"Q3125220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$6BEF5472-8391-483C-8D79-CC4F95A7DEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8695ab8067903991d76b877211314b9ae0d3706","datavalue":{"value":{"entity-type":"item","numeric-id":960514,"id":"Q960514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$D26F6F25-7846-49F3-B177-C8C64F184A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"392907b60e306d2faa3b5505f8451e97e9dbff07","datavalue":{"value":{"entity-type":"item","numeric-id":1336752,"id":"Q1336752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$25B68B81-7321-4A2C-922E-74781BE456CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1acfff9cc0db0552a74f079291e8d7fdd7b0f0f8","datavalue":{"value":{"entity-type":"item","numeric-id":1892104,"id":"Q1892104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$03F45DEB-ED7F-4689-BF7B-FBD87142E9C5","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":"Q5958712$7FD079C6-9323-40BE-B10B-EEBAF13CAF66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c83dfe2ccb91b882717379addb0276d9d17e5ee4","datavalue":{"value":{"entity-type":"item","numeric-id":3031924,"id":"Q3031924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$795D43FB-C990-46A4-87F9-19A824D8FA3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d62d6529573636f59e17c08cac7a0627630d24d","datavalue":{"value":{"entity-type":"item","numeric-id":4032943,"id":"Q4032943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$1738DA49-00E2-4498-8891-A405241944A6","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":"Q5958712$E0CDF7C4-5F9E-4BF0-AF99-7676A35DBBB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$F4DAE459-BE32-49AF-B3C1-59E1E0D39518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7470519bc10f2a005ff140469be5d8d581b53250","datavalue":{"value":{"entity-type":"item","numeric-id":5582060,"id":"Q5582060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$40613567-07DF-4D4E-85BF-8AA2FC537B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"050487ebc7844a3ffa8ba5c0c4ec1da40782b513","datavalue":{"value":{"entity-type":"item","numeric-id":3792237,"id":"Q3792237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$B2B985A6-4376-44BF-A055-12DC5A67C855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a96d0e05946df72ee6628d80821837b8e8483279","datavalue":{"value":{"entity-type":"item","numeric-id":4335203,"id":"Q4335203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$3E07FFD8-D3CD-4D04-A626-512059AAFBAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92aacdaa63d7d729022987f4933a1dd3c8e248ab","datavalue":{"value":{"entity-type":"item","numeric-id":1267197,"id":"Q1267197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958712$9816526C-EA85-46BF-8CD2-07677E092DFE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2aaecc45303912ff1d59feeb06defd540d973b20","datavalue":{"value":{"entity-type":"item","numeric-id":1702659,"id":"Q1702659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbf23167e04670eebf498eae6957fda4a279f7c1","datavalue":{"value":{"amount":"+0.9052443504333496","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":"Q5958712$5EDFC320-53A9-4D1B-8287-D483C3F22A91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05d64b5e10ed1c673e5aae7364671f7465d845aa","datavalue":{"value":{"entity-type":"item","numeric-id":3453280,"id":"Q3453280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54e229968a5f3768f2a90fb5ed176c08c89675c9","datavalue":{"value":{"amount":"+0.8973405957221985","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":"Q5958712$29296328-950A-47B4-A2CF-2A10557C2377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faf20d43e2eed286ae4622a5a12b3311e19046ce","datavalue":{"value":{"entity-type":"item","numeric-id":2450663,"id":"Q2450663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41d99fd258043c18b653d0fc1a7265c996accf38","datavalue":{"value":{"amount":"+0.8873825073242188","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":"Q5958712$7CBC7F08-4741-460F-A95D-65299A3DBC69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8a1914c2716da01548751c53fae96eeffd424a6","datavalue":{"value":{"entity-type":"item","numeric-id":1403343,"id":"Q1403343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da84484f7c0fa5abbe2114bb30763b89f7c4f40","datavalue":{"value":{"amount":"+0.8837944865226746","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":"Q5958712$2310375F-9967-4B62-94AE-3BC96EA3D4C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d01b513de5e405500cf8f798339e5d4e1bb8b1da","datavalue":{"value":{"entity-type":"item","numeric-id":1680492,"id":"Q1680492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4e1389c12bdcc44a97680d6724e701fc260e8a8","datavalue":{"value":{"amount":"+0.8817847967147827","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":"Q5958712$1642CA0B-9F07-4C5D-9C0B-3064A7E8DAB3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958712","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958712"}}}}}