Minimum span frequency allocation problem: A vector bin packing approach

We revisit the minimum span frequency allocation problem (MS-FAP) to address the spectrum scarcity issue in wireless communication networks. The MS-FAP seeks to minimize the gap (span) between the highest and lowest frequencies used, thereby reducing the total bandwidth required in the network while ensuring the demand of each associated link. We formulate the MS-FAP with the physical interference model as a vector bin packing (VBP) problem on a weighted complete directed graph and then leverage conventional heuristic algorithms based on first-fit decreasing (FFD). Extensive computer simulations and analysis results demonstrate that the FFD-based heuristics outperform the state-of-the-art MS-FA algorithm in both performance and computational complexity. In particular, the FFDsum, an item-centric FFD algorithm, generally achieves the best performance for the MS-FAP. This work is noteworthy in that it is the first to apply VBP to the MS-FAP.