Resource title

Fast approximate PCPs for multidimensional bin-packing problem

Resource image

image for OpenScout resource :: Fast approximate PCPs for multidimensional bin-packing problem

Resource description

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(T(n)), where T(n) is the time required to test for heaviness. We give heaviness testers that can test heaviness of an element in the domain [1, ...,n]d in time O((log n)d). We also also give approximate PCPs with efficient verifiers for recursive bin packing and multidimensional routing.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/31236/

Resource license