Knapsack problems with position-dependent item weights or profits. (English) Zbl 1532.90095
Summary: We consider three new knapsack problems with variable weights or profits of items, where the weight or profit of an item depends on the position of the item in the sequence of items packed in the knapsack. We show how to solve the problems exactly using dynamic programming algorithms with pseudo-polynomial running times and propose fully polynomial-time approximation schemes for their approximate solution.
References:
| [1] | Alon, T.; Halman, N., Automatic generation of FPTASes for stochastic monotone dynamic programs made easier, SIAM Journal on Discrete Mathematics, 35, 2679-2722 (2021) · Zbl 1532.90057 · doi:10.1137/19M1308633 |
| [2] | Alon, T.; Halman, N., Strongly polynomial FPTASes for monotone dynamic programs, Algorithmica, 84, 2785-2819 (2022) · Zbl 1541.68441 · doi:10.1007/s00453-022-00954-8 |
| [3] | Cacchiani, V., Iori, M., Locatelli, A., & Martello, S. (2022a). Knapsack problems—An overview of recent advances. Part I: Single knapsack problems. Computers & Operations Research,143, 105692. · Zbl 1512.90189 |
| [4] | Cacchiani, V., Iori, M., Locatelli, A., & Martello, S. (2022b). Knapsack problems—An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research,143, 105693. · Zbl 1512.90190 |
| [5] | Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company. · Zbl 0411.68039 |
| [6] | Gawiejnowicz, S. (2020a). A review of four decades of time-dependent scheduling: main results, new topics, and open problems. Journal of Scheduling,20, 3-47. · Zbl 1434.90057 |
| [7] | Gawiejnowicz, S. (2020b). Models and algorithms of time-dependent scheduling. Springer. · Zbl 1453.90002 |
| [8] | Halman, N.; Klabjan, D.; Li, C-L; Orlin, J.; Simchi-Levi, D., Fully polynomial time approximation schemes for stochastic dynamic programs, SIAM Journal on Discrete Mathematics, 28, 1725-1796 (2014) · Zbl 1408.68078 · doi:10.1137/130925153 |
| [9] | Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Springer. · Zbl 1103.90003 |
| [10] | Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. John Wiley & Sons. · Zbl 0708.68002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
