Geodesic
A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem
Sibirskij žurnal industrialʹnoj matematiki, Tome 21 (2018) no. 2, pp. 108-121.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SJIM_2018_21_2_a9,
     author = {A. B. Khutoretskii and S. V. Bredikhin and A. A. Zamyatin},
     title = {A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem},
     journal = {Sibirskij \v{z}urnal industrialʹnoj matematiki},
     pages = {108--121},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJIM_2018_21_2_a9/}
}
TY  - JOUR
AU  - A. B. Khutoretskii
AU  - S. V. Bredikhin
AU  - A. A. Zamyatin
TI  - A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem
JO  - Sibirskij žurnal industrialʹnoj matematiki
PY  - 2018
SP  - 108
EP  - 121
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJIM_2018_21_2_a9/
LA  - ru
ID  - SJIM_2018_21_2_a9
ER  - 
%0 Journal Article
%A A. B. Khutoretskii
%A S. V. Bredikhin
%A A. A. Zamyatin
%T A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem
%J Sibirskij žurnal industrialʹnoj matematiki
%D 2018
%P 108-121
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJIM_2018_21_2_a9/
%G ru
%F SJIM_2018_21_2_a9
A. B. Khutoretskii; S. V. Bredikhin; A. A. Zamyatin. A lexicographic $0,5$-approximation algorithm for the multiple knapsack problem. Sibirskij žurnal industrialʹnoj matematiki, Tome 21 (2018) no. 2, pp. 108-121. http://geodesic.mathdoc.fr/item/SJIM_2018_21_2_a9/

[1] Martello S., Toth P., Knapsack Problems: Algorithms and Computer Implementations, John Wiley Sons, Chichester–N.Y., 1990 | MR | Zbl

[2] Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer-Verl., Berlin–Heidelberg, 2004 | MR | Zbl

[3] Papadimitriou C., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, Englewood Cliffs, 1982 | MR | Zbl

[4] Chekuri C., Khanna S., “A polynomial time approximation scheme for the multiple knapsack problem”, SIAM J. Computing, 5:3 (2003), 713–728 | DOI | MR

[5] Jansen K., “Parameterized approximation scheme for the multiple knapsack problem”, SIAM J. Computing, 39:4 (2009), 1392–1412 | DOI | MR | Zbl

[6] Dantzig G. D., “Discrete variable extremum problems”, Operations Research, 5:2 (1957), 266–277 | DOI | MR

[7] Mualem A., Nisan N., “Truthful approximation mechanisms for restricted combinatorial auctions”, Games and Economic Behavior, 64:2 (2008), 612–631 | DOI | MR | Zbl