A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)264-277
Number of pages14
JournalJournal of Applied and Industrial Mathematics
Volume12
Issue number2
DOIs
Publication statusPublished - 1 Apr 2018

Keywords

  • approximation algorithm
  • approximation ratio
  • lexicographic ordering
  • multiple knapsack problem

Fingerprint

Dive into the research topics of 'A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem'. Together they form a unique fingerprint.

Cite this