Editing Knapsack problem (section)

=== Online ===
In the '''online knapsack problem''', the items come one by one. Whenever an item arrives, we must decide immediately whether to put it in the knapsack or discard it. There are two variants: (a) non-removable - an inserted item remains in the knapsack forever; (b) removable - an inserted item may be removed later, to make room for a new item.

Han, Kawase and Makino<ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |date=2015-01-11 |title=Randomized algorithms for online knapsack problems |url=https://www.sciencedirect.com/science/article/pii/S0304397514007798 |journal=Theoretical Computer Science |volume=562 |pages=395–405 |doi=10.1016/j.tcs.2014.10.017 |issn=0304-3975}}</ref> present a randomized algorithm for the unweighted non-removable setting. It is 2-competitive, which is the best possible. For the weighted removable setting, they give a 2-competitive algorithm, prove a lower bound of ~1.368 for randomized algorithms, and prove that no deterministic algorithm can have a constant competitive ratio. For the unweighted removable setting, they give an 10/7-competitive-ratio algorithm, and prove a lower  bound of 1.25. 

There are several other papers on the online knapsack problem.<ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |date=2014-09-01 |title=Online Unweighted Knapsack Problem with Removal Cost |url=https://link.springer.com/article/10.1007/s00453-013-9822-z |journal=Algorithmica |language=en |volume=70 |issue=1 |pages=76–91 |doi=10.1007/s00453-013-9822-z |issn=1432-0541}}</ref><ref>{{Cite journal |last1=Han |first1=Xin |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |last4=Guo |first4=He |date=2014-06-26 |title=Online removable knapsack problem under convex function |journal=Theoretical Computer Science |series=Combinatorial Optimization: Theory of algorithms and Complexity |volume=540-541 |pages=62–69 |doi=10.1016/j.tcs.2013.09.013 |issn=0304-3975|doi-access=free }}</ref><ref>{{Citation |last1=Han |first1=Xin |title=Online Knapsack Problems with a Resource Buffer |date=2019-09-22 |arxiv=1909.10016 |last2=Kawase |first2=Yasushi |last3=Makino |first3=Kazuhisa |last4=Yokomaku |first4=Haruki}}</ref>