A polynomial algorithm for the multiple bounded knapsack problem with divisible item sizes is presented. The complexity of the algorithm is O(n2 + nm), where n and m are the number of different item sizes and knapsacks, respectively. It is also shown that the algorithm complexity reduces to O(n logn +nm) when a single copy exists of each item.
Detti, P. (2009). A polynomial algorithm for the multiple knapsack problem with divisible item sizes. INFORMATION PROCESSING LETTERS, 109(11), 582-584 [10.1016/j.ipl.2009.02.003].
A polynomial algorithm for the multiple knapsack problem with divisible item sizes
DETTI, PAOLO
2009-01-01
Abstract
A polynomial algorithm for the multiple bounded knapsack problem with divisible item sizes is presented. The complexity of the algorithm is O(n2 + nm), where n and m are the number of different item sizes and knapsacks, respectively. It is also shown that the algorithm complexity reduces to O(n logn +nm) when a single copy exists of each item.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
IPLDetti.pdf
non disponibili
Descrizione: Articolo
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
129.9 kB
Formato
Adobe PDF
|
129.9 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
Utilizza questo identificativo per citare o creare un link a questo documento:
https://hdl.handle.net/11365/10944
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo