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

Research

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

Links

Text available via DOI:

Keywords

View graph of relations

On upper bounds for the multiple knapsack assignment problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

E-pub ahead of print

Standard

On upper bounds for the multiple knapsack assignment problem. / Galli, Laura; Letchford, Adam.
In: Operations Research Letters, Vol. 54, 107104, 13.03.2024.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Galli, L & Letchford, A 2024, 'On upper bounds for the multiple knapsack assignment problem', Operations Research Letters, vol. 54, 107104. https://doi.org/10.1016/j.orl.2024.107104

APA

Galli, L., & Letchford, A. (2024). On upper bounds for the multiple knapsack assignment problem. Operations Research Letters, 54, Article 107104. Advance online publication. https://doi.org/10.1016/j.orl.2024.107104

Vancouver

Galli L, Letchford A. On upper bounds for the multiple knapsack assignment problem. Operations Research Letters. 2024 Mar 13;54:107104. Epub 2024 Mar 13. doi: 10.1016/j.orl.2024.107104

Author

Galli, Laura ; Letchford, Adam. / On upper bounds for the multiple knapsack assignment problem. In: Operations Research Letters. 2024 ; Vol. 54.

Bibtex

@article{73b43d794dfa41fea6174543fda2713b,
title = "On upper bounds for the multiple knapsack assignment problem",
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.",
keywords = "combinatorial optimisation, knapsack problems, multiple knapsack assignment problem",
author = "Laura Galli and Adam Letchford",
year = "2024",
month = mar,
day = "13",
doi = "10.1016/j.orl.2024.107104",
language = "English",
volume = "54",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On upper bounds for the multiple knapsack assignment problem

AU - Galli, Laura

AU - Letchford, Adam

PY - 2024/3/13

Y1 - 2024/3/13

N2 - 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.

AB - 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.

KW - combinatorial optimisation

KW - knapsack problems

KW - multiple knapsack assignment problem

U2 - 10.1016/j.orl.2024.107104

DO - 10.1016/j.orl.2024.107104

M3 - Journal article

VL - 54

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

M1 - 107104

ER -