
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Computational Complexity Analysis of SetBinPacking Problem
Tomonori IZUMI Toshihiko YOKOMARU Atsushi TAKAHASHI Yoji KAJITANI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E81A
No.5
pp.842849 Publication Date: 1998/05/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: binpacking, complexity, technology mapping, FPGA,
Full Text: PDF(682.7KB)>>
Summary:
The packing problem is to pack given items into given containers as efficiently as possible under various constraints. It is fundamental and significant with variations and applications. The SetBinPacking (SBP) is a class of packing problems: Pack given items into as few bins which have the same capacity where every item is a set and a bin can contain items as long as the number of distinct elements in the union of the items equals to or less than the capacity. One of applications is in FPGA technology mapping, which is our initial motivation. In this paper, the computational complexity of SBP is studied with respect to three parameters α, γ, and δ which are the capacity, the upper bound of the number of elements in an item, and the upper bound of the number of items having an element, respectively. In contrast that the well known IntegerBinPacking (IBP) is NPhard but is proved that even a simplest heuristics FirstFitDecreasing (FFD) outputs exact solutions as long as α 6, our result reveals that SBP remains NPhard for a small values of these parameters. The results are summarized on a 3D map of computational complexities with respect to these three parameters.

