Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009
Approximation algorithms for minimum knapsack problem
Abstract
dc:description.abstractKnapsack 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 and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our experiments show that, the proposed algorithm runs fast and has a good performance ratio in practice. We also conduct extensive experiments on the data provided by Canadian Pacific Logistics Solutions during the MITACS internship program. We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional) minimum knapsack problem and compare its performance with a generalization of a greedy algorithm for minimum knapsack in d dimensions. Our experiments show that the e- approximation scheme exhibits good performance ratio in practice.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Grantor dc:publisher
- Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009
- Year dc:date.issued
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Islam, Mohammad Tauhidul
- University of Lethbridge. Faculty of Arts and Science
- Advisor dc:contributor.supervisor
-
- Gaur, Daya
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10133/1304