| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331148 | Information and Computation | 2005 | 15 Pages |
Abstract
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(logd n) where n is the number of blocks and d is the dimension.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
TuÄkan Batu, Ronitt Rubinfeld, Patrick White,