## 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 × 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) ∈ A × 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 mand n are the sizes of A and B correspondingly.

Original language | English |
---|---|

Pages (from-to) | 264-277 |

Number of pages | 14 |

Journal | Journal of Applied and Industrial Mathematics |

Volume | 12 |

Issue number | 2 |

DOIs | |

Publication status | Published - 1 Apr 2018 |

## Keywords

- approximation algorithm
- approximation ratio
- lexicographic ordering
- multiple knapsack problem