Treffer: Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation

Title:
Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation
Authors:
Song, Yongqiang
Contributors:
Shahrokhi, Farhad, Mihalcea, Rada, 1974-, Seidel, Peter-Michael
Publisher Information:
University of North Texas
Publication Year:
2003
Collection:
University of North Texas: UNT Digital Library
Subject Terms:
Approximation theory, Algorithms, Combinatorial packing and covering, Approximation algorithm, geometric packing problems, VLSI design
Document Type:
Dissertation thesis
File Description:
Text
Language:
English
Relation:
oclc: 54463806; https://digital.library.unt.edu/ark:/67531/metadc4355/; ark: ark:/67531/metadc4355
Availability:
https://digital.library.unt.edu/ark:/67531/metadc4355/
Rights:
Use restricted to UNT Community ; Copyright ; Song, Yongqiang ; Copyright is held by the author, unless otherwise noted. All rights reserved.
Accession Number:
edsbas.77ACCEF9
Database:
BASE

Weitere Informationen

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.