{"entities":{"Q2884299":{"pageid":2895024,"ns":120,"title":"Item:Q2884299","lastrevid":42443432,"modified":"2025-06-27T19:36:11Z","type":"item","id":"Q2884299","labels":{"en":{"language":"en","value":"A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6038613"}},"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":"Q2884299$AF41F7E1-A19C-45F7-8E4F-E98CCEFCE6CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"90cfa8e5904bc452790e019c22ec9b7192d37875","datavalue":{"value":"1246.68265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$8F13A2C2-F3E2-4EF3-8FFC-0CC71D9165AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d20669dfd1f646f116bdcd4edb829ffbf240e456","datavalue":{"value":{"entity-type":"item","numeric-id":203725,"id":"Q203725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2884299$06D0DC6F-165F-4AD0-8769-E122F5E45203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"38a47e2531a4bf8122b29daae2886484554c2a60","datavalue":{"value":{"entity-type":"item","numeric-id":243609,"id":"Q243609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2884299$7C74D4AF-FFA3-4D23-A755-E26B256F5344","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cccce4a4205b51ff587d222bc7a07ed4bfa86d8f","datavalue":{"value":{"entity-type":"item","numeric-id":103831,"id":"Q103831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2884299$4E6EC624-E2C1-45C4-9FEA-6EB234803474","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4dd357d987d60d499edfc98e682fe931160623b6","datavalue":{"value":{"time":"+2012-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2884299$36407377-29DE-491E-819B-45BF6729DE55","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$0B7CB33F-99CF-4099-AEC8-E6939A435252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$8B476057-F942-494A-B52D-F126F24A35C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$A64FDD5F-B2EA-45DB-9609-63384924C6F9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fa9f7a517c609d439bff88bfaf41ea38f7c57dde","datavalue":{"value":"6038613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$9332F9D7-D5EB-4565-9EC5-A71D52ADF93A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93b87bd955a28a4e575dbc4dad978f5378602e4a","datavalue":{"value":"cutting stock problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2884299$47EA013D-64EB-42F5-9FF5-0A2D5ED44E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90ad2d23c1ed42bcf5e3bd1754605a5b060ca641","datavalue":{"value":"bin packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2884299$BA47524B-D015-4F30-9986-EA79A1632447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2884299$F33B6C95-4BD3-4086-9300-C74C6D5CE5E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08823d8721d2e03d88e4cef8093d074f2f680a23","datavalue":{"value":"mixed-integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2884299$D8AF133A-7EAD-4485-B57A-A27EF211E9F1","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":"Q2884299$ABC27B15-D82B-41D7-8010-AED432DDAFD9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"83332dd7a25331bb50280334c6ee39f3884e1aed","datavalue":{"value":"https://doi.org/10.1287/moor.1110.0515","type":"string"},"datatype":"url"},"type":"statement","id":"Q2884299$A013C6FB-424B-4C4E-9CE5-9BC11BB18DE1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d58a745bf69846ccdc064836653a0eff0d0b01da","datavalue":{"value":"W1982112521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$B8457074-8BFC-49A4-A78B-21FD67AF15F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7814567b7ffdb26478ef2e8b8120c396c3bee33","datavalue":{"value":"10.1287/MOOR.1110.0515","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2884299$C558AFC0-8C38-4779-959D-990AE25A404B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"853408f074aa46e73bc82574a34ccdc7094a3a3f","datavalue":{"value":{"entity-type":"item","numeric-id":3569837,"id":"Q3569837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dba3966ab9f7c39b75fbb2a1c0bc4763050810bb","datavalue":{"value":{"amount":"+0.85967255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$FF697741-2017-4764-9143-582F56DA13DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3293c4a2a208b7645e7d9594cee3d9ccc2061ebd","datavalue":{"value":{"entity-type":"item","numeric-id":2900934,"id":"Q2900934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44b331ba0fbcd36009f2c4ecdc20167f36c2e884","datavalue":{"value":{"amount":"+0.8208104","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$22A0ACB4-91F2-4B87-921B-FDA52AE6A622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d633a2eb4d774eaa45aeb737488f4082741b67e1","datavalue":{"value":{"entity-type":"item","numeric-id":4349432,"id":"Q4349432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddbaf0cd6d320c6fedbcf83acdb3a62a2dc7210b","datavalue":{"value":{"amount":"+0.8186099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$9400761C-4DAF-48DE-A8B8-05798E4A0C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1efa15fe3bc4e0306dc93ce476f2209d09c4bf2e","datavalue":{"value":{"entity-type":"item","numeric-id":2643962,"id":"Q2643962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60b134d67fe110d907efb00ca0f4e20028ceba1a","datavalue":{"value":{"amount":"+0.81680626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$06587543-8FF8-4F84-931E-E2FF2A896AD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4a8954807d512ab57dbc5de961376f9ba7da1ec","datavalue":{"value":{"entity-type":"item","numeric-id":868997,"id":"Q868997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88bf2309e7379b843993c4e295210f8845bef02c","datavalue":{"value":{"amount":"+0.8102846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$C383C45B-7104-407F-A65C-B7DC604D24CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb79d9d5e1c2770b98a59a7e6df07211c0029808","datavalue":{"value":{"entity-type":"item","numeric-id":3323652,"id":"Q3323652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"558ccf2cb7be836b80b4c21655057f4880f3e229","datavalue":{"value":{"amount":"+0.80507797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$EAD75F41-0C0C-4919-AAA2-1DA02E368D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3fada6301c3b0ebf19909470fe1587be7807c74","datavalue":{"value":{"entity-type":"item","numeric-id":931915,"id":"Q931915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a161eb1a28e4fcdd4705111957596d291cbf76e4","datavalue":{"value":{"amount":"+0.80165356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$B6F8EE31-54E0-49AB-A79D-B77C820F9151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a505569e2dbb238fd34ae7e353c394df8bff8acd","datavalue":{"value":{"entity-type":"item","numeric-id":4848284,"id":"Q4848284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52149e35773396a6dd504047039a794493b63e28","datavalue":{"value":{"amount":"+0.7999606","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$EB9E0AE0-FFDB-4F60-BBF5-2D979D82D86E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"179652bd0532a8cc55ea8b04f0ffdd459a600131","datavalue":{"value":{"entity-type":"item","numeric-id":1806682,"id":"Q1806682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e8918e2d162703bbf3693d27c90fe5a010dccc3","datavalue":{"value":{"amount":"+0.79807","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$31F3A263-57A8-4626-B03F-3DA5CEE9F6E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2909f863ee5229ac08d959a442eca74d44c6e847","datavalue":{"value":{"entity-type":"item","numeric-id":323473,"id":"Q323473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b864d329310fbb88905c02dd5e11bed80dfa6ff6","datavalue":{"value":{"amount":"+0.79656476","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2884299$3C8BC93E-E109-4CA9-BC4B-D35EF4372E1B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f065547df77bacf61f1d8aca807f79d3c4b39733","datavalue":{"value":{"text":"A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2884299$7969085D-A5A4-4E88-B7E4-A4B58F3F9FD0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"441a5a074206fcd1c0070a9152e67a4c875af43a","datavalue":{"value":"The goal of the cutting stock problem (CSP) is to pack a set \\(\\Omega\\) of \\(n\\) objects into the minimum possible number of bins, each of integer capacity \\(\\beta\\). Objects are of \\(d\\) different types \\(T=\\{T_1, T_2, \\dots,T_d\\}\\), where \\(d\\) is constant and objects of type \\(T_i\\) have positive integer length \\(p_i\\).NEWLINENEWLINEIt is known that CSP is strongly NP-hard, and no approximation algorithm for it can have approximation ratio smaller than 3/2 unless \\(\\mathrm{P}=\\mathrm{NP}\\).NEWLINENEWLINEIn this paper the authors present a polynomial \\(d^{O(d2^d)}\\times 2^{O(8^d)}\\times O((\\log^2n+\\log\\beta)^3\\log^5n)\\) time algorithm that computes a solution using at most one more bin than an optimum solution. The crucial ideas behind the algorithm are the integer programming formulation (IP) for CSP of \\textit{P. C. Gilmore} and \\textit{R. E. Gomory} [Oper. Res. 9, 849--859 (1961; Zbl 0096.35501)]; partitioning the set of objects into large and small ones and rewriting the IP so that only constant number of constraints is needed to restrict the placement of big objects into the bins; and obtaining a mixed-integer program (MIP) with a constant number of integer variables by relaxing integrality constraints on the variables controlling the packing for the small objects.NEWLINENEWLINEFinally, the authors prove that \\textit{H. W. Lenstra jun.}'s algorithm [Math. Oper. Res. 8, 538--548 (1983; Zbl 0524.90067)] can be used to solve MIP in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2884299$7EB4929A-47C3-40F8-A0FF-82C11A481ED5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2884299$F1C1E2BC-BCDF-48E3-8B6B-C8E9E10844E6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2884299","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2884299"}}}}}