Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation

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.

Grantor dc:publisher

University of North Texas

Year dc:date

2003

Author dc:creator

• Song, Yongqiang

Contributors dc:contributor

• Shahrokhi, Farhad
• Mihalcea, Rada, 1974-
• Seidel, Peter-Michael

• Approximation theory.
• Algorithms.
• Combinatorial packing and covering.
• approximation algorithm
• geometric packing problems
• VLSI design
• dynamic programming
• NP-complete problems

Statement dc:rights

• Use restricted to UNT Community
• Copyright
• Song, Yongqiang
• Copyright is held by the author, unless otherwise noted. All rights reserved.

Language dc:language

English

Identifier

oclc: 54463806
https://digital.library.unt.edu/ark:/67531/metadc4355/
ark: ark:/67531/metadc4355

OAI identifier oai:identifier

info:ark/67531/metadc4355