{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:23Z","timestamp":1780822163326,"version":"3.54.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,9]],"date-time":"2014-11-09T00:00:00Z","timestamp":1415491200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00224-014-9566-4","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T06:36:02Z","timestamp":1415946962000},"page":"153-190","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Online Knapsack Revisited"],"prefix":"10.1007","volume":"58","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u0141ukasz","family":"Je\u017c","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,11,9]]},"reference":[{"issue":"2","key":"9566_CR1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-002-0965-6","volume":"34","author":"Y Azar","year":"2002","unstructured":"Azar, Y., Boyar, J., Epstein, L., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: Fair versus unrestricted bin packing. Algorithmica 34(2), 181\u2013196 (2002)","journal-title":"Algorithmica"},{"key":"9566_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Khaitsin, E.: Prompt mechanism for ad placement over time (2011)","DOI":"10.1007\/978-3-642-24829-0_4"},{"key":"9566_CR3","doi-asserted-by":"crossref","unstructured":"Ben-David, S., Borodin, A., Karp, R.M., Tardos, G., Wigderson, A.: On the power of randomization in online algorithms. Algorithmica, 11(1):2\u201314, 1994. Also appeared in. Proc. of the 22nd ACM Symp. on Theory of Comput. (STOC), 379\u2013386 (1990)","DOI":"10.1007\/BF01294260"},{"key":"9566_CR4","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J., Komm, D., Kr\u00e1lovic, R., Rossmanith, P.: On the advice complexity of the knapsack problem (2012)","DOI":"10.1007\/978-3-642-29344-3_6"},{"key":"9566_CR5","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)"},{"issue":"4","key":"9566_CR6","first-page":"463","volume":"8","author":"J Boyar","year":"2001","unstructured":"Boyar, J., Favrholdt, L.M., Larsen, K.S., Nielsen, M.N.: The competitive ratio for on-line dual bin packing with restricted input sequences. Nord. J. Comput. 8(4), 463\u2013472 (2001)","journal-title":"Nord. J. Comput."},{"key":"9566_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Gamzu, I.: Truthful mechanisms via greedy iterative packing (2009)","DOI":"10.1007\/978-3-642-03685-9_5"},{"key":"9566_CR8","doi-asserted-by":"crossref","unstructured":"Han, X., Kawase, Y., Makino, K.: Randomized algorithms for removable online knapsack problems (2013)","DOI":"10.1007\/978-3-642-38756-2_9"},{"key":"9566_CR9","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.tcs.2013.09.013","volume":"540","author":"X Han","year":"2014","unstructured":"Han, X., Kawase, Y., Makino, K., Guo, H.: Online removable knapsack problem under convex function. Theor. Comput. Sci. 540, 62\u201369 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9566_CR10","doi-asserted-by":"crossref","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems (2002)","DOI":"10.1007\/3-540-45465-9_26"},{"issue":"22","key":"9566_CR11","doi-asserted-by":"crossref","first-page":"1016","DOI":"10.1016\/j.ipl.2010.08.013","volume":"110","author":"K Iwama","year":"2010","unstructured":"Iwama, K., Zhang, G.: Online knapsack with resource augmentation. Information Processing Letters 110(22), 1016\u20131020 (2010)","journal-title":"Information Processing Letters"},{"key":"9566_CR12","doi-asserted-by":"crossref","unstructured":"Kalyanasundaram, B., Pruhs, K.: Maximizing job completions online. J. of Algorithms, 49(1):63\u201385, 2003. Also appeared in. Proc. of the 6th European Symp. on Algorithms (ESA), 235\u2013246 (1998)","DOI":"10.1016\/S0196-6774(03)00074-9"},{"key":"9566_CR13","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"issue":"2","key":"9566_CR14","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1006\/jagm.1998.0954","volume":"29","author":"GS Lueker","year":"1998","unstructured":"Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. Also appeared in Proc. of the 6th ACM-SIAM Symp. on Discrete Algorithms (SODA\u201995). J. Algorithms 29(2), 277\u2013305 (1998)","journal-title":"J. Algorithms"},{"key":"9566_CR15","first-page":"73","volume":"68","author":"A Marchetti-Spaccamela","year":"1995","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68, 73\u2013104 (1995)","journal-title":"Math. Program."},{"key":"9566_CR16","unstructured":"Martello, S., Toth, P.: Knapsack problems. John Wiley (1990)"},{"key":"9566_CR17","unstructured":"Noga, J., Sarbua, V.: An online partially fractional knapsack problem (2005)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9566-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9566-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9566-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T05:58:00Z","timestamp":1566021480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9566-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,9]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9566"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9566-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,9]]}}}