Approximation algorithms for minimum knapsack problem

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.