{"entities":{"Q1348737":{"pageid":1359476,"ns":120,"title":"Item:Q1348737","lastrevid":47912023,"modified":"2026-01-03T01:48:51Z","type":"item","id":"Q1348737","labels":{"en":{"language":"en","value":"Polynomial time approximation schemes for class-constrained packing problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1740593"}},"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":"Q1348737$FC3CADFA-441C-422C-BBC6-10E11DD5F0CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8cb10d406620236f28b2bc64095eea2a183c1cc3","datavalue":{"value":{"text":"Polynomial time approximation schemes for class-constrained packing problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1348737$63E31932-A9BF-4192-B5D7-DE28BFDD7D9E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c8551b701fe889654b13ce28fa77a3af3803eb3c","datavalue":{"value":"1028.90048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$C7EF3C91-EF19-4738-B85E-4274D975F276","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b451a2ac0f2c963f77b6135a280741037892792c","datavalue":{"value":{"entity-type":"item","numeric-id":313813,"id":"Q313813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$2239201E-6969-45A8-8943-A7A2C0B6BAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ee54efdfbf5f462a95b8d4096c18ec29b1c41c9","datavalue":{"value":{"entity-type":"item","numeric-id":249088,"id":"Q249088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$032D1119-AE09-4531-B994-9E35C634A17A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39245fc27c04eb23fa7211454c51f34f7f46a9a0","datavalue":{"value":{"entity-type":"item","numeric-id":177699,"id":"Q177699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$B2C6FA17-A8B3-45E0-9210-7707524C3C1A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e51bd21826af75eacea1454cc73c79283c7b8115","datavalue":{"value":{"time":"+2003-07-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1348737$C59C1247-405A-4B76-86BC-83742C003E17","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6c1007e5e31da466d658bc5b021d62f1028f057","datavalue":{"value":"The paper considers generalizations of the classical bin packing and multiple knapsack problems. It is assumed that every item is given a size and a class (a colour). In the class-constrained bin packing (CCBP) problem it is required to minimize the number of bins of the unit size that can be used to pack all items, provided that a bin contains items of no more than a prescribed number of colours. In the class-constrained multiple-knapsack (CCMK) problem each item additionally is given a value (profit), the total number of bins of various sizes is given and it is required to maximize total value of items placed in the bins, provided that the size constraints and the colour constraints are respected. Problem CCMK is shown to admit a polynomial-time approximation scheme (PTAS) that finds a placement with a value at least \\((1-\\varepsilon)\\) times the optimum. Further, problem CCMK with a single bin admits a fully polynomial-time approximation scheme. For problem CCBP a dual PTAS is developed that allows a placement into the optimal number of bins provided that the bin size is extended to \\(1-\\varepsilon\\). On the other hand, if an item can take any colour of a given set of colours, the resulting generalized packing problem becomes APX-hard even in the case of a single bin, equal sizes and equal values of all items.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348737$72AD6861-A45D-402C-BD8D-B197C5F92009","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$11758B44-4208-454E-9AED-66051194BEB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$0BC9FEF1-6996-4A62-B09E-1C2232D1AB77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$642FA8F2-9FE8-46EB-B925-B819615EC955","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6d0216e802d62b86d53651fa9929a3780381f47c","datavalue":{"value":"1740593","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$832EFE3A-6500-47C7-877E-A7AE5C081DD7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c7f47f20fdd5e29cab7d6c70cbd74b86cc707ff","datavalue":{"value":"class-constrained bin packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348737$A6F7D80D-DA57-4033-B002-0D6D26B3566C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c6b799e4078a6aa37a988e66fbbb41f02418547","datavalue":{"value":"class-constrained multiple-knapsack","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348737$F71ED00F-A91F-40A8-8771-D10BA1CC21DB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e656fe06ae7bb4b17f25a82bf69c42b367f81519","datavalue":{"value":{"entity-type":"item","numeric-id":217074,"id":"Q217074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$75D15A0C-07B0-4E7C-A60E-A21E41ECCC80","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":"Q1348737$8A3F840E-5527-4985-AD20-04D9906AC161","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b6db5fe1479e8ebc725fd373757c63348d78d68","datavalue":{"value":"https://doi.org/10.1002/jos.86","type":"string"},"datatype":"url"},"type":"statement","id":"Q1348737$C5E3F2F3-BFDD-4E01-A565-1983079D59D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b728f9b68a111d15e997b17adedb1ca63e54309c","datavalue":{"value":"W2166185745","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$A4F73590-0A88-4200-9F87-B9B58E753D33","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c094423e02d62bc611c7dcb74048d5f57f85de20","datavalue":{"value":{"entity-type":"item","numeric-id":1128680,"id":"Q1128680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$1B1F5FD0-FE7E-45DF-9820-05AADC7F1B4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"330ab4f4f17c0ee4717e95439890535a1926baa1","datavalue":{"value":{"entity-type":"item","numeric-id":4286721,"id":"Q4286721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$58148B2D-A0F1-4DEC-878A-F5F7D5CE5A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecf35bc77ab537b7b8c9013391a44dfa0fd6b169","datavalue":{"value":{"entity-type":"item","numeric-id":1606927,"id":"Q1606927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$652D4D97-B37C-427B-9E1B-292128E7380E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"315ee598c9040e9782bee747455e8ce9a0b9e69c","datavalue":{"value":{"entity-type":"item","numeric-id":4077081,"id":"Q4077081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$B0F5168A-4D3D-4DA5-8C8C-571BA0E2CD85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1abd810edd219852725b067482cec49006a7192","datavalue":{"value":{"entity-type":"item","numeric-id":1238705,"id":"Q1238705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$FABEEC01-1A92-4BD7-AC5D-5BCC24FCB94B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9394fdf11f6181ca5ae7a0e8c2b26aaf35ce9072","datavalue":{"value":{"entity-type":"item","numeric-id":3962774,"id":"Q3962774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$94FA5A59-3CBC-479F-B74A-924822157132","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c1351ebfb47a331a56e7dc9035a42fb1b9dcdd4","datavalue":{"value":{"entity-type":"item","numeric-id":4895625,"id":"Q4895625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$1092543D-4373-4ABD-8BF1-ED22C8329F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d1efe69f60c10f45e7fd491d25c4f4bd44bc5e","datavalue":{"value":{"entity-type":"item","numeric-id":4952619,"id":"Q4952619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$13178F2A-4741-48DC-B656-DFB71057660F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b916828114586c907ab9703174b17d58bf1c2d1","datavalue":{"value":{"entity-type":"item","numeric-id":4114965,"id":"Q4114965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$623839A4-AEF6-4296-83CC-9CBF7A687D79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$E8EB782D-64D9-4C67-8AA1-946CEB63340B","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":"Q1348737$B8835B53-38D5-49E6-872F-560123FBF67A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce192b5f38e2a3bcb2291c730f30437a1c63d1f2","datavalue":{"value":{"entity-type":"item","numeric-id":4938775,"id":"Q4938775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$A8404474-1206-4A61-B6BD-F49AC6DF1B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d873eb220f9c7b9bab911767ca34bf21b911b7c8","datavalue":{"value":{"entity-type":"item","numeric-id":789319,"id":"Q789319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$F219313A-FB1D-4B32-97AA-FD1187701364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64b9b1b720178018e2ed0c7d3bd4c0ddfe4d45f8","datavalue":{"value":{"entity-type":"item","numeric-id":4252288,"id":"Q4252288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$DE6B8ED9-0F15-4C5B-A761-0F23EC6624B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f939c0c65cbd48dada6c2f71c13f0b5233e1ab7","datavalue":{"value":{"entity-type":"item","numeric-id":4095888,"id":"Q4095888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$56D70976-E6E5-4A8F-B357-A257FC2BCA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f164d891b53596eb239fd39c5022993be7e02c87","datavalue":{"value":{"entity-type":"item","numeric-id":1960326,"id":"Q1960326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$9DDE9561-7C3A-47EF-B8F3-FC5C5FD071CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7640c30cc38fbffa71e5661be9033f0cef0d41dd","datavalue":{"value":{"entity-type":"item","numeric-id":1569936,"id":"Q1569936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$29959DF5-ECEF-4966-9F2A-A109D93186F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6ef3aa9ef86c3e63581380c59d3b29eac90e7bb","datavalue":{"value":{"entity-type":"item","numeric-id":5930158,"id":"Q5930158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$B9A6F375-2C8E-4EEE-9D99-95AD4519DAE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b899efa1256565cd547293e33d3ef75f7b23d5b","datavalue":{"value":{"entity-type":"item","numeric-id":4952620,"id":"Q4952620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$F9566E51-033B-42F5-A622-77E4B66F1601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a45dd9e502a15fb0adec8ed068225aa72c2e65bd","datavalue":{"value":{"entity-type":"item","numeric-id":5501827,"id":"Q5501827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$2578C619-5DB5-4E3D-B691-725FBCD584E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5d8710e77e3a71c4bff4c04013e9d4342dabb0a","datavalue":{"value":{"entity-type":"item","numeric-id":1319018,"id":"Q1319018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$A45538E6-ACE4-4FF9-A1AE-31176B79D65F","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":"Q1348737$523B84A7-6B75-48A0-AA68-D1EED416150E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"429924f0ddd3bc1c7dc54a3226f108e3ebc2b532","datavalue":{"value":{"entity-type":"item","numeric-id":922700,"id":"Q922700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348737$090408B3-67A6-46D6-93C5-7313417E926F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af70e2ef40f96cbb42fbeda8a62994fd6154fa5a","datavalue":{"value":"10.1002/JOS.86","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348737$06440F40-63BD-4A89-8346-26F6FFAA5688","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8083fd33778f9e847edddc8c49c30c305041d425","datavalue":{"value":{"entity-type":"item","numeric-id":2753744,"id":"Q2753744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec0aaf5805b3086d4b29988899776e3fc5d98262","datavalue":{"value":{"amount":"+0.9526404738426208","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":"Q1348737$05567F52-B21D-427D-9730-79EAF63EE253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a00298707fe407d0eefe1f812e71654edf9b749","datavalue":{"value":{"entity-type":"item","numeric-id":3591331,"id":"Q3591331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec0aaf5805b3086d4b29988899776e3fc5d98262","datavalue":{"value":{"amount":"+0.9526404738426208","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":"Q1348737$7BE8EB16-2623-450C-9A21-D902CA72AEC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db369a3a677f2575e990c22b41cfdc138b27b51a","datavalue":{"value":{"entity-type":"item","numeric-id":986543,"id":"Q986543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"574b4877786a300508ecf93bdd392abd03e0f24c","datavalue":{"value":{"amount":"+0.8270871639251709","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":"Q1348737$72B55BD2-C59B-40E4-903C-50539D4E879F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"365dd8a16a220c548b603853ce7decede7dd1490","datavalue":{"value":{"entity-type":"item","numeric-id":596145,"id":"Q596145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7755b2bd81f5db9200ebf1d91b562a97b2a9ff74","datavalue":{"value":{"amount":"+0.8236611485481262","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":"Q1348737$7AA51219-D2FE-456E-AA4F-D8B296402A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4af2a935e18b0e0a36ffdf508f51185f4e1e4e65","datavalue":{"value":{"entity-type":"item","numeric-id":5470710,"id":"Q5470710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edb3f8719f7bf1e7b8b6b9063709eb91fbfd0c62","datavalue":{"value":{"amount":"+0.8235527873039246","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":"Q1348737$F66C5ABE-637B-4B51-8D6F-FE0C09086CC8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1348737","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1348737"}}}}}