{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T13:17:03Z","timestamp":1760015823992,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030927011"},{"type":"electronic","value":"9783030927028"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-92702-8_12","type":"book-chapter","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T06:00:24Z","timestamp":1641016824000},"page":"188-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Improved Online Algorithm for Fractional Knapsack in the Random Order Model"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3404-1647","authenticated-orcid":false,"given":"Jeff","family":"Giliberti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6129-3220","authenticated-orcid":false,"given":"Andreas","family":"Karrenbauer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,1]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","unstructured":"Albers, S., Khan, A., Ladewig, L.: Improved online algorithms for knapsack and GAP in the random order model. Algorithmica, February 2021. https:\/\/doi.org\/10.1007\/s00453-021-00801-2","DOI":"10.1007\/s00453-021-00801-2"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.tcs.2021.02.022","volume":"863","author":"S Albers","year":"2021","unstructured":"Albers, S., Ladewig, L.: New results for the k-secretary problem. Theor. Comput. Sci. 863, 102\u2013119 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.02.022","journal-title":"Theor. Comput. Sci."},{"key":"12_CR3","unstructured":"Babaioff, M., Hartline, J., Kleinberg, R.: Selling banner ads: Online algorithms with buyback. In: Fourth Workshop on Ad Auctions (2008)"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling ad campaigns: online algorithms with cancellations. In: Proceedings of the 10th ACM Conference on Electronic Commerce, pp. 61\u201370 (2009)","DOI":"10.1145\/1566374.1566383"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-74208-1_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M Babaioff","year":"2007","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.. P.. (eds.) APPROX\/RANDOM -2007. LNCS, vol. 4627, pp. 16\u201328. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74208-1_2"},{"issue":"6","key":"12_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212512","volume":"65","author":"M Babaioff","year":"2018","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM (JACM) 65(6), 1\u201326 (2018)","journal-title":"J. ACM (JACM)"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.J., Burjons, E., Hromkovi\u010d, J., Lotze, H., Rossmanith, P.: Online simple knapsack with reservation costs. In: Bl\u00e4ser, M., Monmege, B. (eds.) 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 187, pp. 16:1\u201316:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2021.16","DOI":"10.4230\/LIPIcs.STACS.2021.16"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/11561071_61","volume-title":"Algorithms \u2013 ESA 2005","author":"N Buchbinder","year":"2005","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing problems. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 689\u2013701. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11561071_61"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 293\u2013304. IEEE (2006)","DOI":"10.1109\/FOCS.2006.39"},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"B\u00f6ckenhauer, H.J., Komm, D., Kr\u00e1lvi\u010d, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci. 527, 61\u201372 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.01.027","DOI":"10.1016\/j.tcs.2014.01.027"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Chan, T.H.H., Chen, F., Jiang, S.H.C.: Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online $$K$$-item auction and bipartite $$K$$-matching with random arrival order, pp. 1169\u20131188. https:\/\/doi.org\/10.1137\/1.9781611973730.78","DOI":"10.1137\/1.9781611973730.78"},{"key":"12_CR12","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Adaptivity and approximation for stochastic packing problems. In: SODA, vol. 5, pp. 395\u2013404. Citeseer (2005)"},{"key":"12_CR13","doi-asserted-by":"publisher","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsackproblem: the benefit of adaptivity. Math. Oper. Res.33(4), 945\u2013964 (2008). https:\/\/doi.org\/10.1287\/moor.1080.0330","DOI":"10.1287\/moor.1080.0330"},{"key":"12_CR14","first-page":"627","volume":"4","author":"EB Dynkin","year":"1963","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Math. 4, 627\u2013629 (1963)","journal-title":"Soviet Math."},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple o(log log (rank))-competitive algorithm for the matroid secretary problem. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1189\u20131201. SIAM (2014)","DOI":"10.1137\/1.9781611973730.79"},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Goerigk, M., Gupta, M., Ide, J., Sch\u00f6bel, A., Sen, S.: The robust knapsack problem with queries. Comput. Oper. Res. 55, 12\u201322 (2015). https:\/\/doi.org\/10.1016\/j.cor.2014.09.010","DOI":"10.1016\/j.cor.2014.09.010"},{"issue":"1","key":"12_CR17","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s00453-013-9822-z","volume":"70","author":"X Han","year":"2014","unstructured":"Han, X., Kawase, Y., Makino, K.: Online unweighted knapsack problem with removal cost. Algorithmica 70(1), 76\u201391 (2014)","journal-title":"Algorithmica"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.tcs.2014.10.017","volume":"562","author":"X Han","year":"2015","unstructured":"Han, X., Kawase, Y., Makino, K.: Randomized algorithms for online knapsack problems. Theor. Comput. Sci. 562, 395\u2013405 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Han, X., Kawase, Y., Makino, K., Yokomaku, H.: Online Knapsack Problems with a Resource Buffer. In: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 149, pp. 28:1\u201328:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.28","DOI":"10.4230\/LIPIcs.ISAAC.2019.28"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45465-9_26","volume-title":"Automata, Languages and Programming","author":"K Iwama","year":"2002","unstructured":"Iwama, K., Taketomi, S.: Removable Online Knapsack Problems. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) Automata, Languages and Programming, pp. 293\u2013305. Springer, Berlin Heidelberg, Berlin, Heidelberg (2002)"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/978-3-030-64843-5_43","volume-title":"Combinatorial Optimization and Applications","author":"A Karrenbauer","year":"2020","unstructured":"Karrenbauer, A., Kovalevskaya, E.: Reading articles online. In: Wu, W., Zhang, Z. (eds.) COCOA 2020. LNCS, vol. 12577, pp. 639\u2013654. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64843-5_43"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Kesselheim, T., Molinaro, M.: Knapsack secretary with bursty adversary. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol. 168, pp. 72:1\u201372:15. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.72","DOI":"10.4230\/LIPIcs.ICALP.2020.72"},{"key":"12_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-642-40450-4_50","volume-title":"Algorithms \u2013 ESA 2013","author":"T Kesselheim","year":"2013","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Bodlaender, H.L.., Italiano, Giuseppe F.. (eds.) ESA 2013. LNCS, vol. 8125, pp. 589\u2013600. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_50"},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Kesselheim, T., T\u00f6nnis, A., Radke, K., V\u00f6cking, B.: Primal beats dual on online packing LPs in the random-order model. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 303\u2013312. Association for Computing Machinery, New York (2014). https:\/\/doi.org\/10.1145\/2591796.2591810","DOI":"10.1145\/2591796.2591810"},{"key":"12_CR25","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 630\u2013631. Society for Industrial and Applied Mathematics, USA (2005)"},{"issue":"1","key":"12_CR26","first-page":"39","volume":"10","author":"DV Lindley","year":"1961","unstructured":"Lindley, D.V.: Dynamic programming and decision theory. J. Roy. Stat. Soc. Ser. C (Appl. Stat.) 10(1), 39\u201351 (1961)","journal-title":"J. Roy. Stat. Soc. Ser. C (Appl. Stat.)"},{"issue":"2","key":"12_CR27","doi-asserted-by":"publisher","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. J. Algorithms 29(2), 277\u2013305 (1998). https:\/\/doi.org\/10.1006\/jagm.1998.0954","journal-title":"J. Algorithms"},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68(1), 73\u2013104 (1995). https:\/\/doi.org\/10.1007\/BF01585758","DOI":"10.1007\/BF01585758"},{"issue":"1","key":"12_CR29","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(1), 73\u2013104 (1995)","journal-title":"Math. Program."},{"key":"12_CR30","doi-asserted-by":"publisher","unstructured":"Noga, J., Sarbua, V.: An online partially fractional knapsack problem. In: Proceedings of the 8th International Symposium on Parallel Architectures, Algorithms and Networks, pp. 108\u2013112. IEEE Computer Society, Los Alamitos, CA, USA, December 2005. https:\/\/doi.org\/10.1109\/ISPAN.2005.19","DOI":"10.1109\/ISPAN.2005.19"},{"key":"12_CR31","doi-asserted-by":"publisher","unstructured":"Sun, B., Zeynali, A., Li, T., Hajiesmaili, M., Wierman, A., Tsang, D.H.: Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proc. ACM Meas. Anal. Comput. Syst. 4(3), November 2020. https:\/\/doi.org\/10.1145\/3428336","DOI":"10.1145\/3428336"},{"key":"12_CR32","doi-asserted-by":"crossref","unstructured":"Vaze, R.: Online knapsack problem under expected capacity constraint. In: IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp. 2159\u20132167. IEEE (2018)","DOI":"10.1109\/INFOCOM.2018.8485980"},{"issue":"3","key":"12_CR33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/3040230.3040232","volume":"44","author":"R Vaze","year":"2017","unstructured":"Vaze, R., Coupechoux, M.: Online budgeted truthful matching. SIGMETRICS Perform. Eval. Rev. 44(3), 3\u20136 (2017). https:\/\/doi.org\/10.1145\/3040230.3040232","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"12_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-540-92185-1_63","volume-title":"Internet and Network Economics","author":"Y Zhou","year":"2008","unstructured":"Zhou, Y., Chakrabarty, D., Lukose, R.: Budget constrained bidding in keyword auctions and online knapsack problems. In: Papadimitriou, C., Zhang, Shuzhong (eds.) WINE 2008. LNCS, vol. 5385, pp. 566\u2013576. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92185-1_63"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-92702-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T06:23:44Z","timestamp":1641018224000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-92702-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030927011","9783030927028"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-92702-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 January 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lisbon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Portugal","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2021.tecnico.ulisboa.pt\/WAOA2021\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"16","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"52% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}