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, one algorithm is O &parl0;nmk k2mk time and the other is O &parl0;nmk 2e2m/k&parr0; time for any given integer k > 1. Combining the results with the well-known shifting strategy of Hochbaum and Maass, we can derive a (1 - epsilon) times the optimal approximation algorithm for these problems that runs in O (n m 1/(epsilon kk) 2k*k/epsilon time for the first algorithm and O(n m 1/(epsilon 2k) e2/epsilon k3/epsilon) time for the second algorithm on an n x m grid for any given epsilon 1. The best known previous algorithm was due to Hochbaum and Mass and would give (1 - epsilon)2 times the optimal approximation and run in O(k2 (1/epsilon)2 (n m) (1/epsilon)*(1/epsilon) time. The first algorithm was implemented and ran successfully on problems of large input up to 1,000,000 nodes for different values of k and epsilon. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving (1 - epsilon) times optimal 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 k and epsilon. 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.
展开▼
