The Multiple Knapsack Assignment Problem is a strongly NP-hard combinatorial optimisation problem, with several applications. We show that an upper bound for the problem, due to Kataoka and Yamada, can be computed in linear time. We then show that some bounds due to Martello and Monaci dominate the Kataoka-Yamada bound. Finally, we define an even stronger bound, which turns out to be particularly effective when the number of knapsacks is not a multiple of the number of item classes.
Galli L., Letchford A.N. (2024). On upper bounds for the multiple knapsack assignment problem. OPERATIONS RESEARCH LETTERS, 54, 1-6 [10.1016/j.orl.2024.107104].
On upper bounds for the multiple knapsack assignment problem
Galli L.;
2024
Abstract
The Multiple Knapsack Assignment Problem is a strongly NP-hard combinatorial optimisation problem, with several applications. We show that an upper bound for the problem, due to Kataoka and Yamada, can be computed in linear time. We then show that some bounds due to Martello and Monaci dominate the Kataoka-Yamada bound. Finally, we define an even stronger bound, which turns out to be particularly effective when the number of knapsacks is not a multiple of the number of item classes.| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0167637724000403-main.pdf
accesso aperto
Tipo:
Versione (PDF) editoriale
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione
301.6 kB
Formato
Adobe PDF
|
301.6 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
