Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009

Approximation algorithms for minimum knapsack problem

Abstract

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.

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 × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/1304

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Islam, Mohammad Tauhidul; University of Lethbridge. Faculty of Arts and Science. Approximation algorithms for minimum knapsack problem. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009, 2009. https://hdl.handle.net/10133/1304