Computational Complexity Analysis of Set-Bin-Packing Problem

摘要

The packing problem is to pack given items into given containersas efficiently as possible under various con- straints. It isfundamental and significant with variations and applications. TheSet-Bin-Packing (SBP) is a class of packing problems: Pack givenitems into as few bins which have the same capacity where every itemis a sit and a bin can contain items as long as the number ofdistinct elements in the union of the items equals to or less thanthe capacity. One of applications is in FPGA technology mapping,which is our initial motivation.