Fast approximate PCPs for multidimensional bin-packing problems

AbstractWe consider approximate PCPs for multidimensional bin-packing problems. In particular, we show how a verifier can be quickly convinced that a set of multidimensional blocks can be packed into a small number of bins. The running time of the verifier is bounded by O(logdn) where n is the number of blocks and d is the dimension