Skip to main content
SpringerLink
Log in

Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

  • Conference paper
  • First Online:
Computer Science – Theory and Applications (CSR 2018)

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

Included in the following conference series:

Abstract

We study Parallel Task Scheduling \(Pm|size_j|C_{\max }\) with a constant number of machines. This problem is known to be strongly NP-complete for each \(m \ge 5\), while it is solvable in pseudo-polynomial time for each \(m \le 3\). We give a positive answer to the long-standing open question whether this problem is strongly NP-complete for \(m=4\). As a second result, we improve the lower bound of \(\frac{12}{11}\) for approximating pseudo-polynomial Strip Packing to \(\frac{5}{4}\). Since the best known approximation algorithm for this problem has a ratio of \(\frac{4}{3} + \varepsilon \), this result narrows the gap between approximation ratio and inapproximability result by a significant step. Both results are proven by a reduction from the strongly NP-complete problem 3-Partition.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Du, J., Leung, J.Y.: Complexity of scheduling parallel task systems. SIAM J. Discrete Math. 2(4), 473–487 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bansal, N., Correa, J.R., Kenyon, C., Sviridenko, M.: Bin packing in multiple dimensions: inapproximability results and approximation schemes. Math. Oper. Res. 31(1), 31–49 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Adamaszek, A., Kociumaka, T., Pilipczuk, M., Pilipczuk, M.: Hardness of approximation for strip packing. TOCT 9(3), 14:1–14:7 (2017)

    Article  MathSciNet  Google Scholar 

  4. Jansen, K., Rau, M.: Closing the gap for pseudo-polynomial strip packing. CoRR abs/1705.04587 (2017)

    Google Scholar 

  5. Jansen, K., Rau, M.: Improved approximation for two dimensional strip packing with polynomial bounded width. In: Poon, S.-H., Rahman, M.S., Yen, H.-C. (eds.) WALCOM 2017. LNCS, vol. 10167, pp. 409–420. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53925-6_32

    Chapter  Google Scholar 

  6. Gálvez, W., Grandoni, F., Ingala, S., Khan, A.: Improved pseudo-polynomial-time approximation for strip packing. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 9:1–9:14 (2016)

    Google Scholar 

  7. Nadiradze, G., Wiese, A.: On approximating strip packing with a better ratio than 3/2. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1491–1510 (2016)

    Google Scholar 

  8. Jansen, K., Thöle, R.: Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8), 3571–3615 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Amoura, A.K., Bampis, E., Kenyon, C., Manoussakis, Y.: Scheduling independent multiprocessor tasks. Algorithmica 32(2), 247–261 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  10. Jansen, K., Porkolab, L.: Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica 32(3), 507–520 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  11. Garey, M.R., Graham, R.L.: Bounds for multiprocessor scheduling with resource constraints. SIAM J. Comput. 4(2), 187–200 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  12. Turek, J., Wolf, J.L., Yu, P.S.: Approximate algorithms scheduling parallelizable tasks. In: 4th annual ACM symposium on Parallel algorithms and architectures (SPAA), pp. 323–332 (1992)

    Google Scholar 

  13. Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167–176 (1994)

    Google Scholar 

  14. Feldmann, A., Sgall, J., Teng, S.: Dynamic scheduling on parallel machines. Theor. Comput. Sci. 130(1), 49–72 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  15. Jansen, K.: A \((3/2+\varepsilon )\) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In: 24th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 224–235 (2012)

    Google Scholar 

  16. Baker Jr., B.S., Coffman, E.G., Rivest, R.L.: Orthogonal packings in two dimensions. SIAM J. Comput. 9(4), 846–855 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  17. Coffman Jr., E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9(4), 808–826 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  18. Sleator, D.D.: A 2.5 times optimal algorithm for packing in two dimensions. Inf. Proc. Lett. 10(1), 37–40 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  19. Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 290–299. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0049416

    Chapter  Google Scholar 

  20. Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26(2), 401–409 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  21. Harren, R., van Stee, R.: Improved absolute approximation ratios for two-dimensional packing problems. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX/RANDOM -2009. LNCS, vol. 5687, pp. 177–189. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03685-9_14

    Chapter  MATH  Google Scholar 

  22. Harren, R., Jansen, K., Prädel, L., van Stee, R.: A (5/3 + \(\epsilon \))-approximation for strip packing. Comput. Geom. 47(2), 248–267 (2014)

    Article  MathSciNet  Google Scholar 

  23. Golan, I.: Performance bounds for orthogonal oriented two-dimensional packing algorithms. SIAM J. Comput. 10(3), 571–582 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  24. Baker, B.S., Brown, D.J., Katseff, H.P.: A 5/4 algorithm for two-dimensional packing. J. Algorithms 2(4), 348–368 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  25. Kenyon, C., Rémila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Math. Oper. Res. 25(4), 645–656 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  26. Sviridenko, M.: A note on the Kenyon-Remila strip-packing algorithm. Inf. Proc. Lett. 112(1–2), 10–12 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  27. Bougeret, M., Dutot, P., Jansen, K., Robenek, C., Trystram, D.: Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math. Algorithms Appl. 3(4), 553–586 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  28. Jansen, K., Solis-Oba, R.: Rectangle packing with one-dimensional resource augmentation. Discrete Optim. 6(3), 310–323 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  29. Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63–79 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  30. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)

    MATH  Google Scholar 

  31. Henning, S., Jansen, K., Rau, M., Schmarje, L.: Complexity and inapproximability results for parallel task scheduling and strip packing. CoRR abs/1705.04587 (2017)

    Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of the paper. This work was in part supported by German Research Foundation (DFG) project JA 612/14-2.

Author information

Authors and Affiliations

  1. Institut für Informatik, Christian-Albrechts-Universität zu Kiel, Kiel, Germany

    Sören Henning, Klaus Jansen, Malin Rau & Lars Schmarje

Authors
  1. Sören Henning
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Klaus Jansen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Malin Rau
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Lars Schmarje
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Malin Rau .

Editor information

Editors and Affiliations

  1. Department of Informatics, University of Bergen, Bergen, Norway

    Fedor V. Fomin

  2. Steklov Mathematical Institute, Moscow, Russia

    Vladimir V. Podolskii

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Henning, S., Jansen, K., Rau, M., Schmarje, L. (2018). Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing. In: Fomin, F., Podolskii, V. (eds) Computer Science – Theory and Applications. CSR 2018. Lecture Notes in Computer Science(), vol 10846. Springer, Cham. https://doi.org/10.1007/978-3-319-90530-3_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-90530-3_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-90529-7

  • Online ISBN: 978-3-319-90530-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation