On Two Class‐Constrained Versions of the Multiple Knapsack Problem

On Two Class‐Constrained Versions of the Multiple Knapsack Problem

0.00 Avg rating0 Votes
Article ID: iaor20121014
Volume: 29
Issue: 3
Start Page Number: 442
End Page Number: 467
Publication Date: Mar 2001
Journal: Algorithmica
Authors: ,
Keywords: knapsack problem, multimedia, NP-hard
Abstract:

We study two variants of the classic knapsack problem, in which we need to place items of different types 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 class‐constrained multiple knapsack problem (CMKP) we wish to maximize the total number of packed items; in the fair placement problem (FPP) 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.

Reviews

Required fields are marked *. Your email address will not be published.