A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- Authors: Khutoretskii A.B.1, Bredikhin S.V.2, Zamyatin A.A.1
-
Affiliations:
- Novosibirsk State University
- Institute of Computational Mathematics and Mathematical Geophysics
- Issue: Vol 12, No 2 (2018)
- Pages: 264-277
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213048
- DOI: https://doi.org/10.1134/S1990478918020072
- ID: 213048
Cite item
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.
About the authors
A. B. Khutoretskii
Novosibirsk State University
Author for correspondence.
Email: hab@dus.nsc.ru
Russian Federation, ul. Pirogova 2, Novosibirsk, 630090
S. V. Bredikhin
Institute of Computational Mathematics and Mathematical Geophysics
Email: hab@dus.nsc.ru
Russian Federation, pr. Akad. Lavrent’eva 6, Novosibirsk, 630090
A. A. Zamyatin
Novosibirsk State University
Email: hab@dus.nsc.ru
Russian Federation, ul. Pirogova 2, Novosibirsk, 630090