Top

Published in:

2018 | OriginalPaper | Chapter

Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing

Authors : Sören Henning, Klaus Jansen, Malin Rau, Lars Schmarje

Published in: Computer Science – Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Structural Parameterizations of Dominating Set Variants

next chapter Operations on Boolean and Alternating Finite Automata

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

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)MathSciNetCrossRefMATH

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

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

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_32CrossRef

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)

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)

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

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

10.

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

11.

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

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)

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)

14.

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

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)

16.

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

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)MathSciNetCrossRefMATH

18.

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

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/BFb0049416CrossRef

20.

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

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_14CrossRefMATH

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)MathSciNetCrossRef

23.

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

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)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

26.

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

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)MathSciNetCrossRefMATH

28.

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

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)MathSciNetCrossRefMATH

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

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)

Title: Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
Authors: Sören Henning
Klaus Jansen
Malin Rau
Lars Schmarje
Publisher: Springer International Publishing
Book: Computer Science – Theory and Applications
Print ISBN: 978-3-319-90529-7

Electronic ISBN: 978-3-319-90530-3

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-90530-3_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner