Fast approximate PCPs for multidimensional bin-packing problems
We 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(log(d) n) where n is the number of blocks and d is the dimension. (C) 2004 Elsevier Inc. All rights reserved.
multidimensional bin-packing problems proof-assisted property testing probabilistically checkable proofs sublinear-time algorithms