Abstract.
We study two variants of the classic knapsack problem, in which we need to place items of <e5>different types</e5> in multiple knapsacks; each knapsack has a limited capacity, and a bound on the number of different types of items it can hold: in the <e5>class-constrained multiple knapsack problem (CMKP)</e5> we wish to maximize the total number of packed items; in the <e5>fair placement problem (FPP)</e5> our goal is to place the same (large) portion from each set. We look for a perfect placement, in which both problems are solved optimally. We first show that the two problems are NP-hard; we then consider some special cases, where a perfect placement exists and can be found in polynomial time. For other cases, we give approximate solutions. Finally, we give a nearly optimal solution for the CMKP. Our results for the CMKP and the FPP are shown to provide efficient solutions for two fundamental problems arising in multimedia storage subsystems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received June 1, 1998; revised December 5, 1998.
Rights and permissions
About this article
Cite this article
Shachnai, H., Tamir, T. On Two Class-Constrained Versions of the Multiple Knapsack Problem . Algorithmica 29, 442–467 (2001). https://doi.org/10.1007/s004530010057
Issue Date:
DOI: https://doi.org/10.1007/s004530010057