Details

Autor(en) / Beteiligte

• Song, Yongqiang

Titel

Improved approximation algorithms for geometric packing problems with experimental evaluation

Ort / Verlag

ProQuest Dissertations & Theses

Erscheinungsjahr

2003

Link zum Volltext

• ProQuest

Quelle

ProQuest Dissertations & Theses A&I

Beschreibungen/Notizen

• 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[special characters omitted] time and the other is O [special characters omitted] 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 − ϵ) times the optimal approximation algorithm for these problems that runs in O (n m 1/(ϵ kk) 2k*k/ϵ time for the first algorithm and O(n m 1/(ϵ 2k) e2/ϵ k3/ϵ) time for the second algorithm on an n x m grid for any given ϵ < 1. The best known previous algorithm was due to Hochbaum and Mass and would give (1 − ϵ)2 times the optimal approximation and run in O(k2 (1/ϵ)2 (n m) (1/ϵ)*(1/ϵ) 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 ϵ. A heuristic based on the second algorithm is implemented. This heuristic is fast in practice, but may not always be giving (1 − ϵ) 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 ϵ. 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.