{"id":{"repo_id":"unt","oai_identifier":"info:ark/67531/metadc4355"},"canonical_url":"https://search.dev.ndltd.org/etd/unt/info:ark/67531/metadc4355","repository":{"repo_id":"unt","name":"University of North Texas","base_url":"https://digital.library.unt.edu/oai/"},"display":{"title":"Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation","abstract":"Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.","abstract_html":"Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice.","abstract_has_math":false,"creators":["Song, Yongqiang"],"institution":"University of North Texas","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Shahrokhi, Farhad","Mihalcea, Rada, 1974-","Seidel, Peter-Michael"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2003,"date_issued":"2003-12","date_published":"2003-12","updated_at":"2026-07-24T05:35:09Z","subjects":["Approximation theory.","Algorithms.","Combinatorial packing and covering.","approximation algorithm","geometric packing problems","VLSI design","dynamic programming","NP-complete problems"],"languages":["English"],"rights":["Use restricted to UNT Community","Copyright","Song, Yongqiang","Copyright is held by the author, unless otherwise noted. All rights reserved."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["oclc: 54463806","https://digital.library.unt.edu/ark:/67531/metadc4355/","ark: ark:/67531/metadc4355"],"render_values":[{"text":"oclc: 54463806","href":null,"code":true},{"text":"https://digital.library.unt.edu/ark:/67531/metadc4355/","href":"https://digital.library.unt.edu/ark:/67531/metadc4355/","code":true},{"text":"ark: ark:/67531/metadc4355","href":null,"code":true}]}]},"links":{"outbound_url":"https://doi.org/10.12794/metadc4355","outbound_label":"DOI","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Shahrokhi, Farhad","Mihalcea, Rada, 1974-","Seidel, Peter-Michael"]},{"key":"dc:creator","label":"Author","values":["Song, Yongqiang"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2003-12"]},{"key":"dc:publisher","label":"Institution","values":["University of North Texas"]},{"key":"dc:type","label":"Dc Type","values":["Thesis or Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Approximation theory.","Algorithms.","Combinatorial packing and covering.","approximation algorithm","geometric packing problems","VLSI design","dynamic programming","NP-complete problems"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:rights","label":"Dc Rights","values":["Use restricted to UNT Community","Copyright","Song, Yongqiang","Copyright is held by the author, unless otherwise noted. All rights reserved."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["oclc: 54463806","doi: 10.12794/metadc4355","https://digital.library.unt.edu/ark:/67531/metadc4355/","ark: ark:/67531/metadc4355"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice."]},{"key":"dc:format","label":"Dc Format","values":["Text"]},{"key":"dc:title","label":"Title","values":["Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation"]}]}],"canonical_facts":{"dc:contributor":["Shahrokhi, Farhad","Mihalcea, Rada, 1974-","Seidel, Peter-Michael"],"dc:creator":["Song, Yongqiang"],"dc:date":["2003-12"],"dc:description":["Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving optimal times in theory. However, over a wide range of random data this version of the algorithm is giving very good solutions very fast and runs on problems of up to 100,000,000 nodes in a grid and different ranges for the variables. It is also shown that this version of algorithm is clearly superior to the first algorithm and has shown to be very efficient in practice."],"dc:format":["Text"],"dc:identifier":["oclc: 54463806","doi: 10.12794/metadc4355","https://digital.library.unt.edu/ark:/67531/metadc4355/","ark: ark:/67531/metadc4355"],"dc:language":["English"],"dc:publisher":["University of North Texas"],"dc:rights":["Use restricted to UNT Community","Copyright","Song, Yongqiang","Copyright is held by the author, unless otherwise noted. All rights reserved."],"dc:subject":["Approximation theory.","Algorithms.","Combinatorial packing and covering.","approximation algorithm","geometric packing problems","VLSI design","dynamic programming","NP-complete problems"],"dc:title":["Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation"],"dc:type":["Thesis or Dissertation"]},"updated_at":"2026-07-24T05:35:09Z"}