Home > Research > Publications & Outputs > On upper bounds for the multiple knapsack assig...

Associated organisational unit

Electronic data

  • mkap-bounds

    Accepted author manuscript, 357 KB, PDF document

    Embargo ends: 1/01/40

    Available under license: CC BY: Creative Commons Attribution 4.0 International License


Text available via DOI:

View graph of relations

On upper bounds for the multiple knapsack assignment problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

E-pub ahead of print
Article number107104
<mark>Journal publication date</mark>13/03/2024
<mark>Journal</mark>Operations Research Letters
Number of pages6
Publication StatusE-pub ahead of print
Early online date13/03/24
<mark>Original language</mark>English


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.