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 -