Standard

A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem. / Khutoretskii, A. B.; Bredikhin, S. V.; Zamyatin, A. A.

In: Journal of Applied and Industrial Mathematics, Vol. 12, No. 2, 01.04.2018, p. 264-277.

Research output: Contribution to journal › Article › peer-review

Harvard

Khutoretskii, AB, Bredikhin, SV & Zamyatin, AA 2018, 'A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem', Journal of Applied and Industrial Mathematics, vol. 12, no. 2, pp. 264-277. https://doi.org/10.1134/S1990478918020072

APA

Khutoretskii, A. B., Bredikhin, S. V., & Zamyatin, A. A. (2018). A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem. Journal of Applied and Industrial Mathematics, 12(2), 264-277. https://doi.org/10.1134/S1990478918020072

Vancouver

Khutoretskii AB, Bredikhin SV, Zamyatin AA. A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem. Journal of Applied and Industrial Mathematics. 2018 Apr 1;12(2):264-277. doi: 10.1134/S1990478918020072

Author

Khutoretskii, A. B. ; Bredikhin, S. V. ; Zamyatin, A. A. / A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem. In: Journal of Applied and Industrial Mathematics. 2018 ; Vol. 12, No. 2. pp. 264-277.

BibTeX

@article{6e49a3ea470b462985fbbe2f70523c0e,
title = "A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem",
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.",
keywords = "approximation algorithm, approximation ratio, lexicographic ordering, multiple knapsack problem",
author = "Khutoretskii, {A. B.} and Bredikhin, {S. V.} and Zamyatin, {A. A.}",
year = "2018",
month = apr,
day = "1",
doi = "10.1134/S1990478918020072",
language = "English",
volume = "12",
pages = "264--277",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "2",

}

RIS

TY - JOUR

T1 - A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

AU - Khutoretskii, A. B.

AU - Bredikhin, S. V.

AU - Zamyatin, A. A.

PY - 2018/4/1

Y1 - 2018/4/1

N2 - 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.

AB - 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.

KW - approximation algorithm

KW - approximation ratio

KW - lexicographic ordering

KW - multiple knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=85047788519&partnerID=8YFLogxK

U2 - 10.1134/S1990478918020072

DO - 10.1134/S1990478918020072

M3 - Article

AN - SCOPUS:85047788519

VL - 12

SP - 264

EP - 277

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

ER -

ID: 13686315