Improved Hardness of Approximation for Geometric Bin Packing

01/23/2023
by   Arka Ray, et al.
0

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 unit d-dimensional 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 exponential in d, while 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 d^1-ϵ factor unless NP=ZPP. Recently, d-dimensional Vector Bin Packing, a closely related problem to the GBP, was shown to be hard to approximate within Ω(log d) 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 that highlight the difference between Geometric Packing Dimension and Packing Dimension.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset