|
This article is cited in 3 scientific papers (total in 3 papers)
A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem
A. B. Khutoretskiia, S. V. Bredikhinb, A. A. Zamyatina a Novosibirsk State University, 2 Pirogova str., 630090 Novosibirsk
b Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 6 Akad. Lavrentyev av., 630090 Novosibirsk
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.
Keywords:
multiple knapsack problem, lexicographic ordering, approximation algorithm, approximation ratio.
Received: 12.10.2017
Citation:
A. B. Khutoretskii, S. V. Bredikhin, A. A. Zamyatin, “A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem”, Sib. Zh. Ind. Mat., 21:2 (2018), 108–121; J. Appl. Industr. Math., 12:2 (2018), 264–277
Linking options:
https://www.mathnet.ru/eng/sjim1004 https://www.mathnet.ru/eng/sjim/v21/i2/p108
|
Statistics & downloads: |
Abstract page: | 178 | Full-text PDF : | 36 | References: | 27 | First page: | 1 |
|