Abstract
We consider an online knapsack problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online knapsack problem by introducing a dynamic instead of a static knapsack capacity and is applicable to classic problems such as resource allocation or one-way trading. In contrast to the basic online knapsack problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online knapsack problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor.
Similar content being viewed by others
Notes
Note that, for unit incremental capacity \(k=1\), the case of limited weights in \(\{1,\dots ,k\}\) coincides with the unit weight case, so the results shown for unit weights carry over to the limited weight setting if \(k=1\).
Note that, even if one would consider requests that remain valid for several time periods, it would not be advantageous for the adversary to reveal requests that remain valid for more than one period. Therefore, this possibility is not considered in our model.
References
Awerbuch B, Azar Y, Fiat A, Leonardi S, Rosén A (1996) On-line competive algorithms for call admission in optical networks. In: Proceedings of the 4th annual European symposium on algorithms (ESA), LNCS, vol 1136, pp 431–444
Babaioff M, Immorlica N, Kempe D (2007) A knapsack secretary problem with applications. In: Proceedings of the 10th international workshop on approximation algorithms for combinatorial optimization (APPROX), pp 16–28
Bienstock D, Sethuraman J, Ye C (2013) Approximation algorithms for the incremental knapsack problem via disjunctive programming. arXiv.1311.4563
Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge
Disser Y, Klimm M, Megow N, Stiller S (2014) Packing a knapsack of unknown capacity. In: Proceedings of the 31st international symposium on theoretical aspects of computer science (STACS), pp 276–287
El-Yaniv R, Turpin G, Karp R, Fiat A (1992) Competitive analysis of financial games. In: Proceedings of the 33rd annual IEEE symposium on the foundations of computer science (FOCS), pp 327–333
Han X, Kawase Y, Makino K (2015) Randomized algorithms for online knapsack problems. Theor Comput Sci 562:395–405
Hartline J, Sharp A (2006) An incremental model for combinatorial maximization problems. In: Proceedings of the 5th international workshop on experimental and efficient algorithms (WEA), LNCS, vol 4007, pp 36–48
Ibarra OH, Kim CE (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J ACM 22(4):463–468
Ito H, Kiyoshima S, Yoshidy Y (2012) Constant-time approximation algorithms for the knapsack problem. In: Proceedings of the 9th annual conference on theory and applications of models of computation (TAMC), LNCS, vol 7287, pp 131–142
Iwama K, Taketomi S (2002) Removable online knapsack problems. In: Proceedings of the 29th international colloquium on automata, languages and programming (ICALP), pp 293–305
Iwama K, Zhang G (2003) Removable online knapsack-weighted case. In: Proceedings of the 7th Japan–Korea workshop on algorithms and computation (WAAC), pp 223–227
Iwama K, Zhang G (2007) Optimal resource augmentations for online knapsack. In: Proceedings of the 10th international workshop on approximation algorithms for combinatorial optimization (APPROX), pp 180–188
Karp RM (1972) Reducibility among combinatorial problems. In: Proceedings of a symposium on the complexity of computer computations, pp 85–103 (1972)
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, New York
Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper Res 46(1):17–35
Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. J Algorithms 29(2):277–305
Marchetti-Spaccamela A, Vercellis C (1995) Stochastic on-line knapsack problems. Math Progr 68(1–3):73–104
Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, Chichester
Megow N, Mestre J (2013) Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In: Proceedings of the 4th conference on innovations in theoretical computer science (ITCS), pp 495–504
Noga J, Sarbua V (2005) An online partially fractional knapsack problem. In: Proceedings of the 8th international symposium on parallel architectures, algorithms and networks (ISPAN), pp 108–112
Papastavrou JD, Rajagopalan S, Kleywegt AJ (1996) The dynamic and stochastic knapsack problem with deadlines. Manag Sci 42(12):1706–1718
van Slyke R, Young Y (2000) Finite horizon stochastic knapsacks with applications to yield management. Oper Res 48(1):155–172
Yao AC (1977) Probabilistic computations: Toward a unified measure of complexity. In: Proceedings of the 18th annual IEEE symposium on the foundations of computer science (FOCS), pp 222–227
Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. In: Proceedings of the 4th workshop on internet and network economics (WINE), pp 566–576
Author information
Authors and Affiliations
Corresponding author
Additional information
Morten Tiedemann is supported by the German Research Foundation (DFG), Grant GRK 1703/1 for the RTG “Resource Efficiency in Interorganizational Networks”.
Appendix: Proof of Theorem 5
Appendix: Proof of Theorem 5
1.1 Induction I
Base Case: Eq. (7) holds for \(t=2\):
Inductive Step: Let \(t \ge 2,\, t \in {\mathbb {N}}\), be arbitrary and assume that Eq. (7) holds for t (\(\star _1\)). Then, Eq. (7) also holds for \(t+1\):
1.2 Induction II
Base Case: Eq. (8) holds for \(i=2\):
Inductive Step: Let \(i \ge 2,\, i \in {\mathbb {N}}\), be arbitrary and assume that Eq. (8) holds for i (\(\star _2\)). Then, Eq. (8) also holds for \(i+1\):
1.3 Induction III
Base Case: Eq. (10) holds for \(t=2\):
Inductive Step: Let \(t \ge 2,\, t \in {\mathbb {N}}\), be arbitrary and assume that Eq. (10) holds for t (\(\star _3\)). Then, Eq. (10) also holds for \(t+1\):
Rights and permissions
About this article
Cite this article
Thielen, C., Tiedemann, M. & Westphal, S. The online knapsack problem with incremental capacity. Math Meth Oper Res 83, 207–242 (2016). https://doi.org/10.1007/s00186-015-0526-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-015-0526-9