{"id":{"repo_id":"uwo","oai_identifier":"oai:uwo.scholaris.ca:20.500.14721/36962"},"canonical_url":"https://search.dev.ndltd.org/etd/uwo/oai:uwo.scholaris.ca:20.500.14721/36962","repository":{"repo_id":"uwo","name":"Western University","base_url":"https://uwo.scholaris.ca/server/oai/request"},"display":{"title":"High Multiplicity Strip Packing","abstract":"An instance of the two-dimensional strip packing problem is specified by n rectangular items, each having a width, 0 < wn ≤ 1, and height, 0 < hn ≤ 1. The objective is to place these items into a strip of width 1, without rotations, such that they are nonoverlapping and the total height of the resulting packing is minimized. In this thesis, we consider the version of the two-dimensional strip packing problem where there is a constant number K of distinct rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time.","abstract_html":"An instance of the two-dimensional strip packing problem is specified by n rectangular items, each having a width, 0 &lt; wn ≤ 1, and height, 0 &lt; hn ≤ 1. The objective is to place these items into a strip of width 1, without rotations, such that they are nonoverlapping and the total height of the resulting packing is minimized. In this thesis, we consider the version of the two-dimensional strip packing problem where there is a constant number K of distinct rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time.","abstract_has_math":false,"creators":["Price, Devin"],"institution":"The University of Western Ontario","degree_name":"M Sc","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Roberto Solis-Oba"],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-03-13","date_published":"2014-03-13","updated_at":"2026-07-27T21:56:13Z","subjects":["strip packing","approximation algorithm","optimization"],"languages":["en_ca"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14721/36962","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Roberto Solis-Oba"]},{"key":"dc:creator","label":"Author","values":["Price, Devin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-07-10T21:27:58Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-07-10T21:27:58Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-03-13"]},{"key":"dc:publisher","label":"Institution","values":["The University of Western Ontario"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M Sc"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["strip packing","approximation algorithm","optimization"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_ca"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14721/36962"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."]},{"key":"dc:description.abstract","label":"Abstract","values":["An instance of the two-dimensional strip packing problem is specified by n rectangular items, each having a width, 0 < wn ≤ 1, and height, 0 < hn ≤ 1. The objective is to place these items into a strip of width 1, without rotations, such that they are nonoverlapping and the total height of the resulting packing is minimized. In this thesis, we consider the version of the two-dimensional strip packing problem where there is a constant number K of distinct rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time."]},{"key":"dc:title","label":"Title","values":["High Multiplicity Strip Packing"]}]}],"canonical_facts":{"dc:contributor.advisor":["Roberto Solis-Oba"],"dc:creator":["Price, Devin"],"dc:date.accessioned":["2025-07-10T21:27:58Z"],"dc:date.available":["2025-07-10T21:27:58Z"],"dc:date.issued":["2014-03-13"],"dc:description":["The thesis cover page in the PDF document includes references to Western University’s previous institutional repository platform, known as Scholarship@Western, and links to that platform (beginning with ir.lib.uwo.ca). In citing or referring to this thesis, use the DOI or handle from this page instead. Sample citation: Author name, \"Thesis title.\" (Year). Western University Open Repository. https://doi.org/10.71858/123456."],"dc:description.abstract":["An instance of the two-dimensional strip packing problem is specified by n rectangular items, each having a width, 0 < wn ≤ 1, and height, 0 < hn ≤ 1. The objective is to place these items into a strip of width 1, without rotations, such that they are nonoverlapping and the total height of the resulting packing is minimized. In this thesis, we consider the version of the two-dimensional strip packing problem where there is a constant number K of distinct rectangle sizes and present an OPT + K - 1 polynomial-time approximation algorithm for it. This beats a previous algorithm with a worst case bound of OPT + K; the time complexity of that algorithm was not known and here we show that it runs in polynomial time."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14721/36962"],"dc:language.iso":["en_ca"],"dc:publisher":["The University of Western Ontario"],"dc:subject":["strip packing","approximation algorithm","optimization"],"dc:title":["High Multiplicity Strip Packing"],"dc:type":["thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["M Sc"]},"updated_at":"2026-07-27T21:56:13Z"}