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 20 of 184 for “"Knapsack problem"”.
-
The 0 -1 multiple knapsack problem
In operation research, the Multiple Knapsack Problem (MKP) is classified as a combinatorial optimization problem. It is a particular case of the Generalized Assignment Problem. The MKP has been applied to many applications in naval as well as financial management. There are several methods to solve …
-
Approximation algorithms for minimum knapsack problem
Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem, with zero-one maximum knapsack in one dimension being the simplest one. In this thesis we study several existing approximation algorithms for the minimization version of the problem …
-
The unbounded knapsack problem : a critical review
… and datasets in the literature of the Unbounded Knapsack Problem (UKP) is presented in this master's thesis. The algorithms and datasets used are brie y described in this work to provide the reader with basis for understanding the discussions. Some well-known UKP-speci c properties, such as …
-
A complementary heuristic for the unbounded knapsack problem
As a solution algorithm for Unbounded Knapsack Problem, the performance analysis of density-ordered greedy heuristic, weight-ordered greedy heuristic, value-ordered greedy heuristic, extended greedy heuristic and total-value heuristic has been done. Empirical experiments on different test problems …
-
A PTAS for the Uncertain Capacity Knapsack Problem
The standard NP-hard knapsack problem can be interpreted as a scheduling problem with n jobs with weights w1 . . .wn and processing times p1 . . . pn, where our goal is to order the jobs on a single machine so as to maximize the weight of all jobs completing prior to a known common deadline d. In …
-
Allocating Homeland Security Screening Resources Using Knapsack Problem Models
… using discrete optimization models, specifically knapsack problems. The focus of the maritime chapters involves a risk-based approach for prescreening intelligence classifications for primary and secondary screening decisions given limited budget and resources. Results reveal that screening …
-
Generalizations, Extensions, and Applications of the Sequential Knapsack Problem
We consider the Sequential Knapsack Problem (SKP), a special case of the 0-1 Knapsack Problem (KP), where each item size divides the next, without remainder, when arranged from smallest to largest. We present an O(n^2 log n) algorithm that solves SKP and the Bounded Sequential Knapsack Problem …
-
Public key cryptography and the zero-one knapsack problem
… the Merkle-Hellman system based on the zero-one knapsack problem is presented. Standard attacks on the zero-one knapsack problem are rejected as too time-consuming. Herlestam's proposed attack is discussed in detail. The results of theoretical examination and computer tests show that it is not …
-
A branch and exclude algorithm for the knapsack problem.
… and exclude algorithm for solution of the "knapsack problem"... is presented which requires relatively small amounts of computer running time and core storage allocation...
-
Revisiting sparse dynamic programming for the 0/1 Knapsack Problem
The 0/1-Knapsack Problem is a classic NP-hard problem. There are two common approaches to obtain the exact solution: branch-and-bound (BB) and dynamic programming (DP). A socalled, "sparse" DP algorithm (SKPDP) that performs fewer operations than the standard algorithm (KPDP) is well known. To the …
-
Relaxations for the dynamic knapsack problem with stochastic item sizes
We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an …
-
Essays on The Online Multiple Knapsack Problem & The Online Reservation Problem
We study two problems in this thesis, viz. the online multiple knapsack problem (OMKP) and the online reservation problem (ORP). The OMKP has applications in revenue management and scheduling. There are multiple identical knapsacks. Items arrive one at a time, each having a value-density and a …
-
The application of the in-tree knapsack problem to routing prefix caches
… (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever …
-
A Stochastic Approach to Modeling Aviation Security Problems Using the KNAPSACK Problem
… a system response function is introduced and the problem of determining the optimal system response function that minimizes the false alarm rate, while meeting the false clear standard, is formulated as a decision problem and proven to be NP-complete. Two heuristic procedures, the Greedy algorithm …
-
Resource allocation and scheduling strategies using utility and the knapsack problem on computational grids
… business orientations. This dissertation address problems related to the allocation of the computing resources which compose a grid. First, the design of a pan-Canadian grid is presented. The design exploits the maturing stability of grid deployment toolkits, and introduces novel services for …
-
Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem
… of items whose total weight does not exceed the knapsack capacity, and whose profit is a maximum. In the robust KP the goal is to find a subset of items whose total weight does not exceed the knapsack capacity, and remains near maximum for the worst scenario. Solving the robust KP exactly is …
Page 1 of 10