On Two Class-Constrained Versions of the Multiple Knapsack Problem |
| |
Authors: | H Shachnai T Tamir |
| |
Affiliation: | (1) Department of Computer Science, The Technion, Haifa 32000, Israel. \{hadas, tami\}@cs.technion.ac.il., IL |
| |
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.
Received June 1, 1998; revised December 5, 1998. |
| |
Keywords: | , Knapsack, Packing, Approximation algorithms, Resource allocation, Fairness, Utilization, Multimedia on-demand, |
本文献已被 SpringerLink 等数据库收录! |
|