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.
On upper bounds for the multiple knapsack assignment problem
Galli L.;Letchford A. N.
2024-01-01
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 in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
