Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Approximation Algorithms (2)
- Algebraic methods (1)
- Algorithm Analysis (1)
- Analysis of algorithms (1)
- Approximation algorithm (1)
-
- Approximation algorithms (1)
- Artificial neural networks (1)
- Bag Constraints (1)
- Classification (1)
- Combinatorial Optimization (1)
- Computer Games (1)
- Denoising (1)
- Facility Location (1)
- Field of Vision (FOV) (1)
- Genetic algorithms (1)
- Geometric packing problems (1)
- Graph Balancing Problem (1)
- High multiplicity (1)
- High multiplicity strip packing (1)
- Job-Intersection Graph (1)
- K-Cut (1)
- Linear program rounding (1)
- Local Search (1)
- Local alignement (1)
- Multiway Cut (1)
- Neural architecture search (1)
- Normalized similarity metric (1)
- Novelty search (1)
- Optimization (1)
- Patch-based (1)
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
High Multiplicity Strip Packing Problem With Three Rectangle Types, Andy Yu
High Multiplicity Strip Packing Problem With Three Rectangle Types, Andy Yu
Electronic Thesis and Dissertation Repository
The two-dimensional strip packing problem (2D-SPP) involves packing a set R = {r1, ..., rn} of n rectangular items into a strip of width 1 and unbounded height, where each rectangular item ri has width 0 < wi ≤ 1 and height 0 < hi ≤ 1. The objective is to find a packing for all these items, without overlaps or rotations, that minimizes the total height of the strip used. 2D-SPP is strongly NP-hard and has practical applications including stock cutting, scheduling, and reducing peak power demand in smart-grids.
This thesis considers …
High Multiplicity Strip Packing, Andrew Bloch-Hansen
High Multiplicity Strip Packing, Andrew Bloch-Hansen
Electronic Thesis and Dissertation Repository
In the two-dimensional high multiplicity strip packing problem (HMSPP), we are given k distinct rectangle types, where each rectangle type Ti has ni rectangles each with width 0 < wi and height 0 < hi The goal is to pack these rectangles into a strip of width 1, without rotating or overlapping the rectangles, such that the total height of the packing is minimized.
Let OPT(I) be the optimal height of HMSPP on input I. In this thesis, we consider HMSPP for the case when k = 3 and present an OPT(I) + 5/3 polynomial time approximation algorithm for …
New Algorithms For Computing Field Of Vision Over 2d Grids, Evan Debenham
New Algorithms For Computing Field Of Vision Over 2d Grids, Evan Debenham
Electronic Thesis and Dissertation Repository
In many computer games checking whether one object is visible from another is very important. Field of Vision (FOV) refers to the set of locations that are visible from a specific position in a scene of a computer game. Once computed, an FOV can be used to quickly determine the visibility of multiple objects from a given position.
This thesis summarizes existing algorithms for FOV computation, describes their limitations, and presents new algorithms which aim to address these limitations. We first present an algorithm which makes use of spatial data structures in a way which is new for FOV calculation. …
A New Approach To Sequence Local Alignment: Normalization With Concave Functions, Qiang Zhou
A New Approach To Sequence Local Alignment: Normalization With Concave Functions, Qiang Zhou
Electronic Thesis and Dissertation Repository
Sequence local alignment is to find two subsequences from the input two sequences respectively, which can produce the highest similarity degree among all other pairs of subsequences. The Smith-Waterman algorithm is one of the most important technique in sequence local alignment, especially in computational molecular biology. This algorithm can guarantee that the optimal local alignment can be found with respect to the distance or similarity metric. However, the optimal solution obtained by Smith-Waterman is not biologically meaningful, since it may contain small pieces of irrelevant segments, but as long as they are not strong enough, the algorithm still take them …
Algebraic Neural Architecture Representation, Evolutionary Neural Architecture Search, And Novelty Search In Deep Reinforcement Learning, Ethan C. Jackson
Algebraic Neural Architecture Representation, Evolutionary Neural Architecture Search, And Novelty Search In Deep Reinforcement Learning, Ethan C. Jackson
Electronic Thesis and Dissertation Repository
Evolutionary algorithms have recently re-emerged as powerful tools for machine learning and artificial intelligence, especially when combined with advances in deep learning developed over the last decade. In contrast to the use of fixed architectures and rigid learning algorithms, we leveraged the open-endedness of evolutionary algorithms to make both theoretical and methodological contributions to deep reinforcement learning. This thesis explores and develops two major areas at the intersection of evolutionary algorithms and deep reinforcement learning: generative network architectures and behaviour-based optimization. Over three distinct contributions, both theoretical and experimental methods were applied to deliver a novel mathematical framework and experimental …
An Adaptive Weighted Average (Wav) Reprojection Algorithm For Image Denoising, Halimah Alsurayhi
An Adaptive Weighted Average (Wav) Reprojection Algorithm For Image Denoising, Halimah Alsurayhi
Electronic Thesis and Dissertation Repository
Patch-based denoising algorithms have an effective improvement in the image denoising domain. The Non-Local Means (NLM) algorithm is the most popular patch-based spatial domain denoising algorithm. Many variants of the NLM algorithm have proposed to improve its performance. Weighted Average (WAV) reprojection algorithm is one of the most effective improvements of the NLM denoising algorithm. Contrary to the NLM algorithm, all the pixels in the patch contribute into the averaging process in the WAV reprojection algorithm, which enhances the denoising performance. The key parameters in the WAV reprojection algorithm are kept fixed regardless of the image structure. In this thesis, …
Approximation Algorithms For Problems In Makespan Minimization On Unrelated Parallel Machines, Daniel R. Page
Approximation Algorithms For Problems In Makespan Minimization On Unrelated Parallel Machines, Daniel R. Page
Electronic Thesis and Dissertation Repository
A fundamental problem in scheduling is makespan minimization on unrelated parallel machines (R||Cmax). Let there be a set J of jobs and a set M of parallel machines, where every job Jj ∈ J has processing time or length pi,j ∈ ℚ+ on machine Mi ∈ M. The goal in R||Cmax is to schedule the jobs non-preemptively on the machines so as to minimize the length of the schedule, the makespan. A ρ-approximation algorithm produces in polynomial time a feasible solution such that its objective value is within a multiplicative factor ρ of …
Local Search Approximation Algorithms For Clustering Problems, Nasim Samei
Local Search Approximation Algorithms For Clustering Problems, Nasim Samei
Electronic Thesis and Dissertation Repository
In this research we study the use of local search in the design of approximation algorithms for NP-hard optimization problems. For our study we have selected several well-known clustering problems: k-facility location problem, minimum mutliway cut problem, and constrained maximum k-cut problem.
We show that by careful use of the local optimality property of the solutions produced by local search algorithms it is possible to bound the ratio between solutions produced by local search approximation algorithms and optimum solutions. This ratio is known as the locality gap.
The locality gap of our algorithm for the k-uncapacitated facility …