The computational complexity of the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems and their multiple variants were studied in numerous papers in the past where all the weights and profits were assumed to be integers. We re-examine here the computational complexity of all these problems in the setting where the weights and profits are allowed to be any rational numbers. We show that all of these problems in this setting become strongly NP-complete and, as a result, no pseudo-polynomial algorithm can exist for solving them unless P = NP. Despite this result we show that they all still admit a fully polynomial-time approximation scheme.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others ReferencesBabat, L.G.: Linear functions on n-dimensional unit cube. Doklady Akademii Nauk SSSR 221(4), 761–762 (1975)
Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713–728 (2005)
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158. ACM (1971)
Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: On the computational complexity of weighted voting games. Ann. Math. Artif. Intell. 56(2), 109–131 (2009)
Gallo, G., Hammer, P.L., Simeone, B.: Quadratic knapsack problems. In: Padberg, M.W. (ed.) Combinatorial Optimization, pp. 132–149. Springer, Heidelberg (1980). https://doi.org/10.1007/BFb0120892
Garey, M.R., Johnson, D.S.: “Strong” NP-completeness results: motivation, examples, and implications. J. ACM (JACM) 25(3), 499–508 (1978)
Guéret, C., Prins, C.: A new lower bound for the open-shop problem. Ann. Oper. Res. 92, 165–183 (1999)
Hoogeveen, J.A., Oosterhout, H., van de Velde, S.L.: New lower and upper bounds for scheduling around a small common due date. Oper. Res. 42(1), 102–110 (1994)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM (JACM) 22(4), 463–468 (1975)
Johnson, D.S., Niemi, K.A.: On knapsacks, partitions, and a new dynamic programming technique for trees. Math. Oper. Res. 8(1), 1–14 (1983)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complex. Comput. Comput., pp. 85–103. Springer, Heidelberg (1972)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24777-7
Levin, L.A.: Universal sequential search problems. Problemy Peredachi Informatsii 9(3), 115–116 (1973)
Mathews, G.B.: On the partition of numbers. Proc. Lond. Math. Soc. 1(1), 486–490 (1897)
Mousa, M.A.A., Schewe, S., Wojtczak, D.: Optimal control for simple linear hybrid systems. In: Proceedings of TIME, pp. 12–20. IEEE Computer Society (2016)
Mousa, M.A.A., Schewe, S., Wojtczak, D.: Optimal control for multi-mode systems with discrete costs. In: Abate, A., Geeraerts, G. (eds.) FORMATS 2017. LNCS, vol. 10419, pp. 77–96. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-65765-3_5
Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233–249 (2009)
Pisinger, D.: An exact algorithm for large multiple knapsack problems. Eur. J. Oper. Res. 114(3), 528–541 (1999)
Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Ill. J. Math. 6(1), 64–94 (1962)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216–226. ACM (1978)
Silvano, M., Paolo, T.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Hoboken (1990)
Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8(1), 85–89 (1984)
Vazirani, V.V.: Approximation Algorithms. Springer Science & Business Media, Heidelberg (2013). https://doi.org/10.1007/978-3-662-04565-7
We would like to thank the anonymous reviewers whose comments helped to improve this paper. This work was partially supported by the EPSRC through grants EP/M027287/1 (Energy Efficient Control) and EP/P020909/1 (Solving Parity Games in Theory and Practice).
Author information Authors and AffiliationsUniversity of Liverpool, Liverpool, UK
Dominik Wojtczak
Correspondence to Dominik Wojtczak .
Editor information Editors and AffiliationsDepartment of Informatics, University of Bergen, Bergen, Norway
Fedor V. Fomin
Steklov Mathematical Institute, Moscow, Russia
Vladimir V. Podolskii
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper Cite this paperWojtczak, D. (2018). On Strong NP-Completeness of Rational Problems. 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_26
Download citationDOI: https://doi.org/10.1007/978-3-319-90530-3_26
Published: 25 April 2018
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-90529-7
Online ISBN: 978-3-319-90530-3
eBook Packages: Computer ScienceComputer Science (R0)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4