A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

A. B. Khutoretskii, S. V. Bredikhin, A. A. Zamyatin

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

1 Цитирования (Scopus)


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.

Язык оригиналаанглийский
Страницы (с-по)264-277
Число страниц14
ЖурналJournal of Applied and Industrial Mathematics
Номер выпуска2
СостояниеОпубликовано - 1 апр. 2018


Подробные сведения о темах исследования «A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem». Вместе они формируют уникальный семантический отпечаток (fingerprint).