{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:24:26Z","timestamp":1761294266013,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T00:00:00Z","timestamp":1613520000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T00:00:00Z","timestamp":1613520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"European Research Council","award":["691672"],"award-info":[{"award-number":["691672"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["691672","691672"],"award-info":[{"award-number":["691672","691672"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Projekt DEAL"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>knapsack problem<\/jats:italic> is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. In the online setting, items are revealed one by one and the decision, if the current item is packed or discarded forever, must be done immediately and irrevocably upon arrival. We study the online variant in the random order model where the input sequence is a uniform random permutation of the item set. We develop a randomized (1\/6.65)-competitive algorithm for this problem, outperforming the current best algorithm of competitive ratio 1\/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939\u20131964, 2018). Our algorithm is based on two new insights: We introduce a novel algorithmic approach that employs two given algorithms, optimized for restricted item classes, sequentially on the input sequence. In addition, we study and exploit the relationship of the knapsack problem to the 2-secretary problem. The <jats:italic>generalized assignment problem<\/jats:italic> (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. We show that in the same online setting, applying the proposed sequential approach yields a (1\/6.99)-competitive randomized algorithm for GAP. Again, our proposed algorithm outperforms the current best result of competitive ratio 1\/8.06 (Kesselheim et al. in SIAM J Comput 47(5):1939\u20131964, 2018).<\/jats:p>","DOI":"10.1007\/s00453-021-00801-2","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T13:37:49Z","timestamp":1613741869000},"page":"1750-1785","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Improved Online Algorithms for Knapsack and GAP in the Random Order Model"],"prefix":"10.1007","volume":"83","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"given":"Arindam","family":"Khan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5998-8154","authenticated-orcid":false,"given":"Leon","family":"Ladewig","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,17]]},"reference":[{"key":"801_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"key":"801_CR2","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)"},{"key":"801_CR3","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.cosrev.2016.12.001","volume":"24","author":"HI Christensen","year":"2017","unstructured":"Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63\u201379 (2017)","journal-title":"Comput. Sci. Rev."},{"key":"801_CR4","doi-asserted-by":"crossref","unstructured":"G\u00e1lvez, W., Grandoni, F., Heydrich, S., Ingala, S., Khan, A., Wiese, A.: Approximating geometric knapsack via L-packings. In: Proceedings of 58th IEEE annual symposium on foundations of computer science (FOCS), pp. 260\u2013271 (2017)","DOI":"10.1109\/FOCS.2017.32"},{"issue":"3","key":"801_CR5","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. (SICOMP) 35(3), 713\u2013728 (2005)","journal-title":"SIAM J. Comput. (SICOMP)"},{"issue":"2","key":"801_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., Vazirani, V.V.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127(2), 255\u2013267 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"801_CR7","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1284320.1284321","volume":"54","author":"A Mehta","year":"2007","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized online matching. J. ACM 54(5), 22 (2007)","journal-title":"J. ACM"},{"key":"801_CR8","doi-asserted-by":"crossref","unstructured":"Feldman, J., Korula, N., Mirrokni, V.S., Muthukrishnan, S., P\u00e1l, M.: Online ad assignment with free disposal. In: Proceedings of 5th international workshop internet and network economics (WINE), pp 374\u2013385 (2009)","DOI":"10.1007\/978-3-642-10841-9_34"},{"issue":"3","key":"801_CR9","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0377-2217(92)90077-M","volume":"60","author":"DG Cattrysse","year":"1992","unstructured":"Cattrysse, D.G., Wassenhove, L.N.V.: A survey of algorithms for the generalized assignment problem. Eur. J. Oper. Res. 60(3), 260\u2013272 (1992)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"801_CR10","first-page":"123","volume":"45","author":"T \u00d6ncan","year":"2007","unstructured":"\u00d6ncan, T.: A survey of the generalized assignment problem and its applications. Inf. Syst. Oper. Res. INFOR 45(3), 123\u2013141 (2007)","journal-title":"Inf. Syst. Oper. Res. INFOR"},{"key":"801_CR11","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J.T., Immorlica, N., Jain, K., Etesami, O., Mahdian, M.: Dynamics of bid optimization in online advertisement auctions. In: Proceedings of 16th International Conference on World Wide Web (WWW), pp 531\u2013540 (2007)","DOI":"10.1145\/1242572.1242644"},{"key":"801_CR12","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Chakrabarty, D., Lukose, R.M.: Budget constrained bidding in keyword auctions and online knapsack problems. In: Proceedings 4th international workshop internet and network economics (WINE), pp 566\u2013576 (2008)","DOI":"10.1007\/978-3-540-92185-1_63"},{"key":"801_CR13","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. Sov. Math. 4, 627\u2013629 (1963)","journal-title":"Sov. Math."},{"key":"801_CR14","doi-asserted-by":"publisher","first-page":"39","DOI":"10.2307\/2985407","volume":"10","author":"DV Lindley","year":"1961","unstructured":"Lindley, D.V.: Dynamic programming and decision theory. Appl. Stat. 10, 39\u201351 (1961)","journal-title":"Appl. Stat."},{"key":"801_CR15","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM 65(6), 35:1-35:26 (2018)","DOI":"10.1145\/3212512"},{"issue":"2","key":"801_CR16","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1287\/moor.2017.0876","volume":"43","author":"M Feldman","year":"2018","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. Math. Oper. Res. 43(2), 638\u2013650 (2018)","journal-title":"Math. Oper. Res."},{"key":"801_CR17","doi-asserted-by":"crossref","unstructured":"Chan, T.H., Chen, F., Jiang, S.H.: Revealing optimal thresholds for generalized secretary problem via continuous LP: impacts on online K-item auction and bipartite K-matching with random arrival order. In: Proceedings of 26th annual ACM-siam symposium on discrete algorithms (SODA), pp 1169\u20131188 (2015)","DOI":"10.1137\/1.9781611973730.78"},{"key":"801_CR18","unstructured":"Kleinberg, R.D.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of 16th Annual ACM-SIAM symposium on discrete algorithms (SODA), pp 630\u2013631 (2005)"},{"key":"801_CR19","unstructured":"Albers, S., Janke, M.: Scheduling in the random-order model. In: Proceedings of 47th international colloquium on automata, languages, and programming, (ICALP) 2020, pp 68:1\u201368:18 (2020)"},{"key":"801_CR20","doi-asserted-by":"crossref","unstructured":"G\u00f6bel, O., Kesselheim, T., T\u00f6nnis, A.: Online appointment scheduling in the random order model. In: Proceedings 23rd annual European symposium on algorithms (ESA), pp 680\u2013692 (2015)","DOI":"10.1007\/978-3-662-48350-3_57"},{"key":"801_CR21","doi-asserted-by":"crossref","unstructured":"Molinaro, M.: Online and random-order load balancing simultaneously. In: P.N. Klein (ed.) Proceedings 28th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM. pp 1638\u20131650 (2017)","DOI":"10.1137\/1.9781611974782.108"},{"issue":"4","key":"801_CR22","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876\u2013890 (2014)","journal-title":"Oper. Res."},{"key":"801_CR23","doi-asserted-by":"crossref","unstructured":"Feldman, J., Henzinger, M., Korula, N., Mirrokni, V.S., Stein, C.: Online stochastic packing applied to display ad allocation. In: Proceedings 18th annual european symposium on algorithms (ESA), pp 182\u2013194 (2010)","DOI":"10.1007\/978-3-642-15775-2_16"},{"key":"801_CR24","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: Proceedings of 7th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 359\u2013364 (1996)"},{"issue":"5","key":"801_CR25","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/15M1033708","volume":"47","author":"T Kesselheim","year":"2018","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: Primal beats dual on online packing LPs in the random-order model. SIAM J. Comput. 47(5), 1939\u20131964 (2018)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"801_CR26","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1287\/moor.2013.0612","volume":"39","author":"M Molinaro","year":"2014","unstructured":"Molinaro, M., Ravi, R.: The geometry of online packing linear programs. Math. Oper. Res. 39(1), 46\u201359 (2014)","journal-title":"Math. Oper. Res."},{"key":"801_CR27","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Mehta, A., Motwani, R.: A 1.43-competitive online graph edge coloring algorithm in the random order arrival model. In: Proceedings of 21st annual ACM-SIAM symposium on discrete algorithms (SODA), pp 31\u201339 (2010)","DOI":"10.1137\/1.9781611973075.4"},{"key":"801_CR28","doi-asserted-by":"crossref","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: Proceedings of 21st annual European symposium on algorithms (ESA), pp 589\u2013600 (2013)","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"801_CR29","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: Proceedings of 43rd annual ACM symposium on theory of computing (STOC), pp 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"801_CR30","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proceedings of 42nd IEEE annual symposium on foundations of computer science (FOCS), pp 426\u2013431 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"801_CR31","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Gharan, S.O., Zadimoghaddam, M.: Simultaneous approximations for adversarial and stochastic online budgeted allocation. In: Proceedings of 23rd annual ACM-SIAM symposium on discrete algorithms (SODA), pp 1690\u20131701 (2012)","DOI":"10.1137\/1.9781611973099.134"},{"issue":"3","key":"801_CR32","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1137\/15M1051142","volume":"47","author":"N Korula","year":"2018","unstructured":"Korula, N., Mirrokni, V.S., Zadimoghaddam, M.: Online submodular welfare maximization: greedy beats 1\/2 in random order. SIAM J. Comput. 47(3), 1056\u20131086 (2018)","journal-title":"SIAM J. Comput."},{"key":"801_CR33","first-page":"73","volume":"68","author":"A Marchetti-Spaccamela","year":"1995","unstructured":"Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Progr. 68, 73\u2013104 (1995)","journal-title":"Stochastic on-line knapsack problems. Math. Progr."},{"key":"801_CR34","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Proceedings of 10th international workshop on approximation, randomization, and combinatorial optimization and 11th international workshop on randomization and computation (APPROX\/RANDOM), pp 16\u201328 (2007)","DOI":"10.1007\/978-3-540-74208-1_2"},{"key":"801_CR35","first-page":"1","volume":"2017","author":"R Vaze","year":"2017","unstructured":"Vaze, R.: Online knapsack problem and budgeted truthful bipartite matching. Proc. IEEE Conf. Comput. Commun. (INFOCOM) 2017, 1\u20139 (2017)","journal-title":"Proc. IEEE Conf. Comput. Commun. (INFOCOM)"},{"issue":"2","key":"801_CR36","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)","journal-title":"J. Algorithms"},{"key":"801_CR37","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":"801_CR38","doi-asserted-by":"crossref","unstructured":"Iwama, K., Taketomi, S.: Removable online knapsack problems. In: Proceedings of 29th international colloquium on automata, languages and programming (ICALP), pp 293\u2013305 (2002)","DOI":"10.1007\/3-540-45465-9_26"},{"key":"801_CR39","unstructured":"Babaioff, M., Hartline, J., Kleinberg, R.: Selling banner ads: online algorithms with buyback. In: Fourth workshop on ad auctions (2008)"},{"key":"801_CR40","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Hartline, J.D., Kleinberg, R.D.: Selling ad campaigns: online algorithms with cancellations. In: Proceedings of 10th ACM conference on electronic commerce (EC), pp 61\u201370 (2009)","DOI":"10.1145\/1566374.1566383"},{"issue":"1","key":"801_CR41","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":"801_CR42","first-page":"2159","volume":"2018","author":"R Vaze","year":"2018","unstructured":"Vaze, R.: Online knapsack problem under expected capacity constraint. Proc. IEEE Conf. Comput. Commun. (INFOCOM) 2018, 2159\u20132167 (2018)","journal-title":"Proc. IEEE Conf. Comput. Commun. (INFOCOM)"},{"key":"801_CR43","doi-asserted-by":"crossref","unstructured":"Alaei, S., Hajiaghayi, M., Liaghat, V.: The online stochastic generalized assignment problem. In: Proceedings of 16th international workshop on approximation, randomization, and combinatorial optimization and 17th international workshop on randomization and computation (APPROX\/RANDOM), pp 11\u201325 (2013)","DOI":"10.1007\/978-3-642-40328-6_2"},{"issue":"2","key":"801_CR44","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"key":"801_CR45","unstructured":"Albers, S., Ladewig, L.: New results for the k-secretary problem. In: Proceedings of 30th international symposium on algorithms and computation (ISAAC), pp 18:1\u201318:19 (2019)"},{"issue":"1","key":"801_CR46","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/1122023","volume":"22","author":"M Nikolaev","year":"1977","unstructured":"Nikolaev, M.: On a generalization of the best choice problem. Theory Probab. Appl. 22(1), 187\u2013190 (1977)","journal-title":"Theory Probab. Appl."},{"issue":"4","key":"801_CR47","doi-asserted-by":"publisher","first-page":"803","DOI":"10.2307\/3213146","volume":"16","author":"M Tamaki","year":"1979","unstructured":"Tamaki, M.: Recognizing both the maximum and the second maximum of a sequence. J. Appl. Prob. 16(4), 803\u2013812 (1979)","journal-title":"J. Appl. Prob."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00801-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00801-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00801-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:04:09Z","timestamp":1621937049000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00801-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,17]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["801"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00801-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,2,17]]},"assertion":[{"value":"21 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}