We address a variant of the continuous knapsack problem, where capacities regarding costs of items are given into account. We prove that the problem is NP-complete although the classical continuous knapsack problem is solvable in linear time. For the case that there exists exactly one capacity for all items, we solve the corresponding problem in O(n log n) time, where n is the number of items.
Huynh Duc Quoc, Nguyen Chi Tam, Tran Hoai Ngoc Nhan
. The Continuous Knapsack Problem with Capacities[J]. Journal of the Operations Research Society of China, 2021
, 9(3)
: 713
-721
.
DOI: 10.1007/s40305-020-00298-6
[1] Skiena, S.:The Stony Brook Algorithm Repository. Springer, Berlin (1997)
[2] Martello, S., Toth, P.:Knapsack Problems:Algorithms and Computer Implementations. Wiley, Chichester (1990)
[3] Kellerer, H., Pferschy, U., Pisinger, D.:Knapsack Problem. Springer, Berlin (2004)
[4] Csirik, J., Frenk, H., Labbé, M., Zhang, S.:Heuristics for the 0-1 min-knapsack problem. Acta Cybern. 10, 15-20(1991)
[5] Malaguti, E., Monaci, M., Paronuzzi, P., Pferschy, U.:Integer optimization with penalized fractional values:the knapsack case. Eur. J. Oper. Res. 273, 874-888(2019)
[6] Burkard, R.E., Pleschiutschnig, C., Zhang, J.Z.:Inverse median problems. Discrete Optim. 1, 23-39(2004)
[7] Nguyen, K.T., Chi, N.T.L.:A model for the inverse 1-median problem on trees under uncertain costs. Opusc. Math. 36, 513-523(2016)
[8] Brickell, E.F.:Breaking iterated knapsacks. Adv. Cryptol. Proc. CRYPTO 84, 342-358(1985)
[9] Lenstra, H.W.:Lattices. In:Algorithmic Number Theory:Lattices, Number Fields, Curves and Cryptography. Mathematical Sciences Research Institute Publications, vol 44, pp 127-181. Cambridge University Press, Cambridge (2008)
[10] Drezner, Z., Mehrez, A., Wesolowsky, G.O.:The facility location problem with limited distances. Transp. Sci. 25, 183-187(1991)
[11] Liu, T.Y., Jiang, H.:Minimizing sum of truncated convex functions and its applications. J. Comput. Graph. Stat. 28, 1-10(2019)
[12] Balas, E., Zemel, E.:An algorithm for large zero-one knapsack problems. Oper. Res. 28, 1130-1154(1980)
[13] Garey, M.R., Johnson, D.S.:Computers and Intractability:A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., Sanfrancisco (1979)
