A polynomial time approximation scheme for the Multiple Knapsack Problem
In: Randomization, approximation, and combinatorial optimization : algorithms and techniques (Berkeley CA, 8-11 August 1999)Lecture notes in computer science :51-62
Konferenz
- print, 4 ref
Zugriff:
The Multiple Knapsack Problem (MKP) (with equal capacities) can be defined as follows: Given a set of n items with positive integer weights and profits, a subset has to be selected such that the items in this subset can be packed into m knapsacks of equal capacities and such that the total profit of all items in the knapsacks is maximized. For m = 1 (MKP) reduces to the classical 0-1 single knapsack problem. It is known that (MKP) admits no fully polynomial-time approximation scheme even for m = 2 unless P = NP. In this paper we present a polynomial time approximation scheme for (MKP) even if m is part of the input. This solves an important open problem in the field of knapsack problems.
Titel: |
A polynomial time approximation scheme for the Multiple Knapsack Problem
|
---|---|
Autor/in / Beteiligte Person: | KELLERER, H |
Link: | |
Quelle: | Randomization, approximation, and combinatorial optimization : algorithms and techniques (Berkeley CA, 8-11 August 1999)Lecture notes in computer science :51-62 |
Veröffentlichung: | Berlin: Springer, 1999 |
Medientyp: | Konferenz |
Umfang: | print, 4 ref |
ISSN: | 0302-9743 (print) |
Schlagwort: |
|
Sonstiges: |
|