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"”.

  1. 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 …

    laurentian Repository record for The 0 -1 multiple knapsack problem (opens in a new tab)

  2. 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 …

    lethbridge Repository record for Approximation algorithms for minimum knapsack problem (opens in a new tab)

  3. 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 …

    brazil-ufrgs Repository record for The unbounded knapsack problem : a critical review (opens in a new tab)

  4. 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 …

    vu-aus Download PDF for A complementary heuristic for the unbounded knapsack problem (opens in a new tab)

  5. 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 …

    clemson Repository record for A PTAS for the Uncertain Capacity Knapsack Problem (opens in a new tab)

  6. 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 …

    vcu Repository record for Allocating Homeland Security Screening Resources Using Knapsack Problem Models (opens in a new tab)

  7. 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 …

    buffalo Repository record for Generalizations, Extensions, and Applications of the Sequential Knapsack Problem (opens in a new tab)

  8. 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 …

    carleton Repository record for Public key cryptography and the zero-one knapsack problem (opens in a new tab)

  9. 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...

    nps Repository record for A branch and exclude algorithm for the knapsack problem. (opens in a new tab)

  10. 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 …

    colostate Repository record for Revisiting sparse dynamic programming for the 0/1 Knapsack Problem (opens in a new tab)

  11. 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 …

    gatech Repository record for Relaxations for the dynamic knapsack problem with stochastic item sizes (opens in a new tab)

  12. 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 …

    umn Repository record for Essays on The Online Multiple Knapsack Problem & The Online Reservation Problem (opens in a new tab)

  13. 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 …

    waterloo Repository record for The application of the in-tree knapsack problem to routing prefix caches (opens in a new tab)

  14. 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 …

    vt Repository record for A Stochastic Approach to Modeling Aviation Security Problems Using the KNAPSACK Problem (opens in a new tab)

  15. 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 …

    uvic Repository record for Resource allocation and scheduling strategies using utility and the knapsack problem on computational grids (opens in a new tab)

  16. 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 …

    utc Repository record for Robust optimization of linear optimization problems and an approximation approach to solve robust Knapsack Problem (opens in a new tab)

Page 1 of 10