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.
| Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc4355 |
| Date | 12 1900 |
| Creators | Song, Yongqiang |
| Contributors | Shahrokhi, Farhad, Mihalcea, Rada, 1974-, Seidel, Peter-Michael |
| Publisher | University of North Texas |
| Source Sets | University of North Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | Text |
| Rights | Use restricted to UNT Community, Copyright, Song, Yongqiang, Copyright is held by the author, unless otherwise noted. All rights reserved. |
Page generated in 0.0021 seconds