Approximation algorithms for minimum knapsack problem

Simple item page
dc.contributor.authorIslam, Mohammad Tauhidul
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.date.accessioned2011-06-24T19:24:19Z
dc.date.available2011-06-24T19:24:19Z
dc.date.issued2009
dc.degree.levelMasters
dc.descriptionx, 85 leaves ; 29 cmen_US
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.en_US
dc.identifier.urihttps://hdl.handle.net/10133/1304
dc.language.isoen_USen_US
dc.publisherLethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009en_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectKnapsack problem (Mathematics)en_US
dc.subjectAlgorithmsen_US
dc.subjectMathematical optimizationen_US
dc.subjectComputational complexityen_US
dc.subjectLinear programmingen_US
dc.subjectInteger programmingen_US
dc.titleApproximation algorithms for minimum knapsack problemen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ISLAM_MOHAMMED_MSC_2009.pdf
Size:
1.02 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.63 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses