A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
| Autor: | A. B. Khutoretskii, A. A. Zamyatin, S. V. Bredikhin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Applied Mathematics
05 social sciences Sorting Approximation algorithm 0102 computer and information sciences Lexicographical order 01 natural sciences Industrial and Manufacturing Engineering Combinatorics Set (abstract data type) 010201 computation theory & mathematics Lexicographic preferences Knapsack problem 0502 economics and business Order (group theory) Size ratio 050207 economics Mathematics |
| Zdroj: | Journal of Applied and Industrial Mathematics. 12:264-277 |
| ISSN: | 1990-4797 1990-4789 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink