Improved hardness of approximation for Geometric Bin Packing

• Published in: Information processing letters 2025-03, Vol.189, p.106552, Article 106552
• Main Authors: Ray, Arka, Sandeep, Sai
• Format: Article
• Language: English
• ISSN: 0020-0190
• DOI: 10.1016/j.ipl.2024.106552

The Geometric Bin Packing (GBP) problem is a generalization of Bin Packing where the input is a set of d-dimensional rectangles, and the goal is to pack them into d-dimensional unit cubes efficiently. It is NP-hard to obtain a PTAS for the problem, even when d=2. For general d, the best-known approximation algorithm has an approximation guarantee that is exponential in d. In contrast, the best hardness of approximation is still a small constant inapproximability from the case when d=2. In this paper, we show that the problem cannot be approximated within a d1−ϵ factor unless NP=P. Recently, d-dimensional Vector Bin Packing, a problem closely related to the GBP, was shown to be hard to approximate within a Ω(log⁡d) factor when d is a fixed constant, using a notion of Packing Dimension of set families. In this paper, we introduce a geometric analog of it, the Geometric Packing Dimension of set families. While we fall short of obtaining similar inapproximability results for the Geometric Bin Packing problem when d is fixed, we prove a couple of key properties of the Geometric Packing Dimension which highlight fundamental differences between Geometric Bin Packing and Vector Bin Packing. •When the dimension is part of the input, Geometric Bin Packing is hard.•Techniques used in Vector Bin Packing to show hardness are unlikely to work here.•Geometric packing dimension, an analog of packing dimension, is introduced.