Show simple item record

dc.contributor.supervisor Gaur, Daya
dc.contributor.author Islam, Mohammad Tauhidul
dc.contributor.author University of Lethbridge. Faculty of Arts and Science
dc.date.accessioned 2011-06-24T19:24:19Z
dc.date.available 2011-06-24T19:24:19Z
dc.date.issued 2009
dc.identifier.uri https://hdl.handle.net/10133/1304
dc.description x, 85 leaves ; 29 cm en_US
dc.description.abstract 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 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. en_US
dc.language.iso en_US en_US
dc.publisher Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009 en_US
dc.relation.ispartofseries Thesis (University of Lethbridge. Faculty of Arts and Science) en_US
dc.subject Knapsack problem (Mathematics) en_US
dc.subject Algorithms en_US
dc.subject Mathematical optimization en_US
dc.subject Computational complexity en_US
dc.subject Linear programming en_US
dc.subject Integer programming en_US
dc.title Approximation algorithms for minimum knapsack problem en_US
dc.type Thesis en_US
dc.publisher.faculty Arts and Science en_US
dc.publisher.department Department of Mathematics and Computer Science en_US
dc.degree.level Masters


Files in this item

This item appears in the following Collection(s)

Show simple item record