Return to search

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.

Identiferoai:union.ndltd.org:unt.edu/info:ark/67531/metadc4355
Date12 1900
CreatorsSong, Yongqiang
ContributorsShahrokhi, Farhad, Mihalcea, Rada, 1974-, Seidel, Peter-Michael
PublisherUniversity of North Texas
Source SetsUniversity of North Texas
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
FormatText
RightsUse restricted to UNT Community, Copyright, Song, Yongqiang, Copyright is held by the author, unless otherwise noted. All rights reserved.

Page generated in 0.0018 seconds