Technical Report CS0966

Title: Polynomial Time Approximation Schemes for Class-Constrained Packing Problems
Authors: Hadas Shachnai and Tami Tamir
PDFNot Available
Abstract: We consider variants of the classic bin packing and multiple knapsack problems, in which sets of elements of {\em different types (colors)} need to be placed in containers; the elements may have different sizes and values. Each container has a limited capacity, and a bound on the number of distinct types of elements it can hold. In the {\em class-constrained multiple knapsack problem (CCMK)} we wish to maximize the total value of packed elements; in the {\em class-constrained bin-packing problem (CCBP)} we wish to minimize the number of (identical) bins needed for packing all the elements. Both the CCMK and the CCBP are strongly NP-Hard for general inputs. We introduce a general method for packing with class constraints, when the values of the elements are proportional to their sizes. We use this method for deriving dual approximation schemes, for both the CCMK and the CCBP. Finally, we show that the 0-1 class-constrained knapsack problem admits a fully polynomial time approximation scheme, even when the bound on the number of distinct colors that can be packed depends on the input size. Our two optimization problems have several important applications, including storage management for multimedia systems, scheduling tasks on processors with limited number of configurations, and scheduling parallelizable tasks on a multiprocessor.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1999
To the main CS technical reports page

Computer science department, Technion