Abstract:
We present a $0{.}5$-approximation algorithm for the Multiple Knapsack Problem (MKP). The algorithm uses the ordering of knapsacks according to the nondecreasing of size and the two orderings of items: in nonincreasing utility order and in nonincreasing order of the utility/size ratio. These orderings create two lexicographic orderings on $A\times B$ (here $A$ is the set of knapsacks and $B$ is the set of indivisible items). Based on each of these lexicographic orderings, the algorithm creates a feasible solution to the MKP by looking through the pairs $(a,b)\in A\times B$ in the corresponding order and placing item $b$ into knapsack $a$ if this item is not placed yet and there is enough free space in the knapsack. The algorithm chooses the best of the two obtained solutions. This algorithm is $0{.}5$-approximate and has runtime $O(mn)$ (without sorting), where $m$ and $n$ are the sizes of $A$ and $B$ correspondingly.
Fulltext:
PDF file (316 kB)