A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- Авторлар: Khutoretskii A.1, Bredikhin S.2, Zamyatin A.1
-
Мекемелер:
- Novosibirsk State University
- Institute of Computational Mathematics and Mathematical Geophysics
- Шығарылым: Том 12, № 2 (2018)
- Беттер: 264-277
- Бөлім: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213048
- DOI: https://doi.org/10.1134/S1990478918020072
- ID: 213048
Дәйексөз келтіру
Аннотация
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.
Авторлар туралы
A. Khutoretskii
Novosibirsk State University
Хат алмасуға жауапты Автор.
Email: hab@dus.nsc.ru
Ресей, ul. Pirogova 2, Novosibirsk, 630090
S. Bredikhin
Institute of Computational Mathematics and Mathematical Geophysics
Email: hab@dus.nsc.ru
Ресей, pr. Akad. Lavrent’eva 6, Novosibirsk, 630090
A. Zamyatin
Novosibirsk State University
Email: hab@dus.nsc.ru
Ресей, ul. Pirogova 2, Novosibirsk, 630090