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(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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. J. of the ACM 45(3), 501–555 (1998)
Batu, T., Rubinfeld, R., White, P.: Fast approximate PCPs for multidimensional bin-packing problems, http://simon.cs.cornell.edu/home/ronitt/PAP/bin.ps
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 3–40 (1991)
Babai, L., Fortnow, L., Lund, C., Szegedy, M.: Checking computations in polylogarithmic time. In: Proc. 31st Foundations of Computer Science, pp. 16–25 (1990)
Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved Testing Algorithms for Monotonicity. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol. 1671, pp. 97–108. Springer, Heidelberg (1999)
Ergun, F., Kannan, S., Kumar, R., Rubinfeld, R., Viswanathan, M.: Spot-checkers. In: Proc. 30th Symposium on Theory of Computing, pp. 259–268 (1998)
Ergün, F., Kumar, R., Rubinfeld, R.: Fast PCPs for approximations. In: Proc. 31st Symposium on Theory of Computing (1999)
Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. Theoretical Computer Science 134(2), 545–557 (1994)
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D.: Testing Monotonicity. In: Proc. 39th Symposium on Foundations of Computer Science (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Batu, T., Rubinfeld, R., White, P. (1999). Fast Approximate PCPs for Multidimensional Bin-Packing Problems. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds) Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 1999 1999. Lecture Notes in Computer Science, vol 1671. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48413-4_25
Download citation
DOI: https://doi.org/10.1007/978-3-540-48413-4_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66329-4
Online ISBN: 978-3-540-48413-4
eBook Packages: Springer Book Archive