SpringerLink
Log in

Packing Cubes into a Cube Is NP-Hard in the Strong Sense

  • Conference paper
Computing and Combinatorics (COCOON 2013)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7936))

Included in the following conference series:

  • 1885 Accesses

Abstract

While the problem of packing two-dimensional squares into a square, in which a set of squares is packed into a big square, has been proved to be NP-complete, the computational complexity of the d-dimensional (d > 2) problems of packing hypercubes into a hypercube remains an open question [5,7]. In this paper, we show that the three-dimensional problem version of packing cubes into a cube is NP-hard in the strong sense.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes. Mathematics of Operations Research 31(1), 31–49 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Caprara, A., Lodi, A., Monaci, M.: Fast Approximation Schemes for Two-stage, Two-dimensional Bin Packing. Mathematics of Operations Research 30, 136–156 (2005)

    Article  MathSciNet  Google Scholar 

  3. Chung, F.R.K., Garey, M.R., Johnson, D.S.: On Packing Two-dimensional Bins. SIAM Journal on Algebraic and Discrete Methods 3, 66–76 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  4. Correa, J.R., Kenyon, C.: Approximation Schemes for Multidimensional Packing. In: Proc. 15th ACM–SIAM Symposium on Discrete Algorithms, pp. 179–188 (2004)

    Google Scholar 

  5. Epstein, L., van Stee, R.: Online Square and Cube Packing. Acta Informatica 41(9), 595–606 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  6. Garey, M., Johnson, D.: Computer and Intractability – A Guide to the Theory of NP-Completeness. Freeman, New York (1979)

    Google Scholar 

  7. Harren, R.: Approximation Algorithms for Orthogonal Packing Problems for Hypercubes. Theoretical Computer Science 410(44), 4504–4532 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Kohayakawa, Y., Miyazawa, F.K., Raghavan, P., Wakabayashi, Y.: Multidimensional Cube Packing. Algorithmica 40, 173–187 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  9. Leung, J.Y.-T., Tam, W.T., Wong, C.S., Chin, F.Y.L.: Packing Squares into a Square. Journal of Parallel and Distributed Computing 10, 271–275 (1990)

    Article  MathSciNet  Google Scholar 

  10. Li, K., Cheng, K.H.: Complexity of Resource Allocation and Job Scheduling Problems in Partitionable Mesh Connected Systems. In: Proc. of 1st Annual IEEE Symposium of Parallel and Distributed Processing, Silver Spring, MD, pp. 358–365 (1989)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mechanical / Electronic and Control Engineering, Bei**g Jiaotong University, Bei**g, 100044, China

    Yi** Lu & Jianzhong Cha

  2. Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN, 46556, USA

    Danny Z. Chen

Authors
  1. Yi** Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Danny Z. Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jianzhong Cha
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Texas at Dallas, 75080, Richardson, TX, USA

    Ding-Zhu Du

  2. College of Computer Science and Technology, Zhejiang University, 310027, Hangzhou, China

    Guochuan Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lu, Y., Chen, D.Z., Cha, J. (2013). Packing Cubes into a Cube Is NP-Hard in the Strong Sense. In: Du, DZ., Zhang, G. (eds) Computing and Combinatorics. COCOON 2013. Lecture Notes in Computer Science, vol 7936. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38768-5_53

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-38768-5_53

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-38767-8

  • Online ISBN: 978-3-642-38768-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation