Computational Complexity Analysis of Set-Bin-Packing Problem

Tomonori IZUMI, Toshihiko YOKOMARU, Atsushi TAKAHASHI, Yoji KAJITANI

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 Set-Bin-Packing (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 Integer-Bin-Packing (IBP) is NP-hard but is proved that even a simplest heuristics First-Fit-Decreasing (FFD) outputs exact solutions as long as α 6, our result reveals that SBP remains NP-hard for a small values of these parameters. The results are summarized on a 3D map of computational complexities with respect to these three parameters.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.5 pp.842-849
• Publication Date: 1998/05/25
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Authors

Tomonori IZUMI
Toshihiko YOKOMARU
Atsushi TAKAHASHI
Yoji KAJITANI

Keyword

bin-packing,  complexity,  technology mapping,  FPGA