{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:20:15Z","timestamp":1772119215074,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["6636-548083-2020"],"award-info":[{"award-number":["6636-548083-2020"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2020-06423"],"award-info":[{"award-number":["RGPIN-2020-06423"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s00224-025-10217-y","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T00:25:30Z","timestamp":1743639930000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["High Multiplicity Strip Packing with Three Rectangle Types"],"prefix":"10.1007","volume":"69","author":[{"given":"Andrew","family":"Bloch-Hansen","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Solis-Oba","sequence":"additional","affiliation":[]},{"given":"Andy","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,1]]},"reference":[{"issue":"4","key":"10217_CR1","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B Baker","year":"1980","unstructured":"Baker, B., Coffman, E., Rivest, R.: Orthogonal packings in two dimensions. SIAM Journal on Computing 9(4), 846\u2013855 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"10217_CR2","unstructured":"Bloch-Hansen, A.: High multiplicity strip packing. Msc. Thesis, Western University (2019)"},{"key":"10217_CR3","doi-asserted-by":"crossref","unstructured":"Bloch-Hansen, A., Solis-Oba, R., Yu, A.: High multiplicity strip packing with three rectangle types. Paper presented at Combinatorial Optimization: 7th International Symposium, ISCO 2022, Online, 2022","DOI":"10.21203\/rs.3.rs-1976126\/v1"},{"issue":"4","key":"10217_CR4","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E Coffman","year":"1980","unstructured":"Coffman, E., Garey, M., Johnson, D., Tarjan, R.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing 9(4), 808\u2013826 (1980)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"10217_CR5","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W De La Vega","year":"1981","unstructured":"De La Vega, W., Lueker, G.: Bin packing can be solved within $$1 + \\epsilon $$ in linear time. Combinatorica 1(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"issue":"1\u20133","key":"10217_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0166-218X(97)00130-3","volume":"82","author":"F De La Vega","year":"1998","unstructured":"De La Vega, F., Zissimopoulos, V.: An approximation scheme for strip packing of rectangles with bounded dimensions. Discrete Applied Mathematics 82(1\u20133), 93\u2013101 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"10217_CR7","unstructured":"Garey, M., and Johnson, D.: Computers and intractability. Vol. 174. San Francisco: freeman (1979)"},{"key":"10217_CR8","doi-asserted-by":"crossref","unstructured":"Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 177-189. Springer, (2009)","DOI":"10.1007\/978-3-642-03685-9_14"},{"issue":"2","key":"10217_CR9","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.comgeo.2013.08.008","volume":"47","author":"R Harren","year":"2014","unstructured":"Harren, R., Jansen, K., Pr\u00e4del, L., Van Stee, R.: A ($$\\frac{5}{3} + \\epsilon $$)-approximation for strip packing. Computational Geometry 47(2), 248\u2013267 (2014)","journal-title":"Computational Geometry"},{"key":"10217_CR10","unstructured":"Karloff, H.: Linear programming. Springer Science & Business Media (2008)"},{"issue":"3","key":"10217_CR11","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.disopt.2009.04.001","volume":"6","author":"K Jansen","year":"2009","unstructured":"Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discrete Optimization 6(3), 310\u2013323 (2009)","journal-title":"Discrete Optimization"},{"key":"10217_CR12","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.: An efficient approximation scheme for the one-dimensional bin-packing problem. In: 23rd Annual Symposium on Foundations of Computer Science, 312\u2013320. IEEE (1982)","DOI":"10.1109\/SFCS.1982.61"},{"issue":"4","key":"10217_CR13","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","volume":"25","author":"C Kenyon","year":"2000","unstructured":"Kenyon, C., R\u00e9mila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research 25(4), 645\u2013656 (2000)","journal-title":"Mathematics of Operations Research"},{"key":"10217_CR14","doi-asserted-by":"crossref","unstructured":"Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. European Symposium on Algorithms, 290-299. Springer, Berlin, Heidelberg (1994)","DOI":"10.1007\/BFb0049416"},{"key":"10217_CR15","doi-asserted-by":"crossref","unstructured":"Sleator, D.: A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Letters. 10(1), 37-40 (1980)","DOI":"10.1016\/0020-0190(80)90121-0"},{"issue":"1\u20132","key":"10217_CR16","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.ipl.2011.10.003","volume":"112","author":"M Sviridenko","year":"2012","unstructured":"Sviridenko, M.: A note on the Kenyon-Remila strip-packing algorithm. Information Processing Letters. 112(1\u20132), 10\u201312 (2012)","journal-title":"Information Processing Letters."},{"issue":"2","key":"10217_CR17","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539793255801","volume":"26","author":"A Steinberg","year":"1997","unstructured":"Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM Journal on Computing 26(2), 401\u2013409 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"10217_CR18","unstructured":"Yu, A.: High Multiplicity Strip Packing Problem With Three Rectangle Types. Msc. Thesis, Western University (2019)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10217-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10217-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10217-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T06:27:35Z","timestamp":1751956055000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10217-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10217"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10217-y","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-1976126\/v1","asserted-by":"object"}]},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,1]]},"assertion":[{"value":"14 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Andrew Bloch-Hansen: research of this author was partially supported by the Natural Sciences and Engineering Research Council of Canada, grant 6636-548083-2020. Roberto Solis-Oba: research of this author was partially supported by the Natural Sciences and Engineering Research Council of Canada, grant RGPIN-2020-06423.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}