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.

Authors

• Tuğkan Batu
• Ronitt Rubinfeld
• Patrick White

Keywords

• Proof-assisted property testing
• Probabilistically checkable proofs
• Multidimensional bin-packing problems
• Sublinear-time algorithms