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. / x, 85 leaves ; 29 cm
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:ALU.w.uleth.ca/dspace#10133/1304 |
| Date | January 2009 |
| Creators | Islam, Mohammad Tauhidul, University of Lethbridge. Faculty of Arts and Science |
| Contributors | Gaur, Daya |
| Publisher | Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009, Arts and Science, Department of Mathematics and Computer Science |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Relation | Thesis (University of Lethbridge. Faculty of Arts and Science) |
Page generated in 0.002 seconds