Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 9 of 9 for “"Geometric packing"”.
-
Approximation Algorithms for Geometric Packing Problems
… approximation algorithms for two-dimensional, geometric packing problems. We have given a set of rectangles that have to be placed in one or several predetermined target regions. Such packing problems can be found in several branches of industry, for example when placing logic elements on a …
-
An Optimization Approach to a Geometric Packing Problem
We investigate several geometric packing problems (derived from an industrial setting) that involve fitting patterns of regularly spaced disks without overlap. We first derive conditions for achieving the feasible placement of a given set of patterns and construct a network formulation that, under …
-
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 …
-
Extremal and Algorithmic Results for Bipartite Graphs via Ferrers Dimension and Axis-Parallel Geometry
… study of structured graph classes arising from geometric representations. A central theme is that mild geometric restrictions often impose a strong combinatorial structure, which can be leveraged to obtain both extremal bounds and improved algorithmic guarantees for classical hard problems. The …
-
Improved approximation algorithms for packing and scheduling problems
This thesis presents approximation algorithms for geometric packing and scheduling problems. First, improved AFPTAS for the Bin Packing Problem (BP) and its generalization, the Variable-sized Bin Packing Problem (VBP), are explained. Our algorithms have to solve the unbounded variant of the …
-
Ab initio methods for protein structure prediction
… energy function OPUS-Ca or a knowledge-based geometric packing potential is used to guide the folding process. The newest version of VecFold is demonstrated to modestly outperform Rosetta, one of the leading ab initio predictors, on the CASP8 benchmark set. In our protein domain boundary …
-
The Topology and Electronic Stability of Solvent-Rich Metallic Glasses
… ability of solvent rich glasses based on geometric packing efficiency/ cluster models that focus on structural aspects of glass-formation and electro-chemical aspects of the constituents based on electronic contributions and magic number theory. The specific rules that dictate …
-
Organization principles of the early Drosophila embryo
… that cortical migration is essentially a nuclear packing problem resulting from uniformly expanding nuclear shell or the energids. The division orientation distribution can accurately predict how many nuclei will make it to the next shell, suggesting that the division orientation controls the …
-
Approximation algorithms for multidimensional bin packing
The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies. In the classical bin packing problem, we are given a list of real numbers in the range (0, 1], the goal is to place them in a minimum number of bins so …