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.
2009
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].
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