Improved Online Algorithm for Fractional Knapsack in the Random Order Model | SpringerLink
Skip to main content
Springer Nature Link
Log in

Improved Online Algorithm for Fractional Knapsack in the Random Order Model

  • Conference paper
  • First Online:
Approximation and Online Algorithms (WAOA 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12982))

Included in the following conference series:

Abstract

The fractional knapsack problem is one of the classical problems in combinatorial optimization, which is well understood in the offline setting. However, the corresponding online setting has been handled only briefly in the theoretical computer science literature so far, although it appears in several applications. Even the previously best known guarantee for the competitive ratio was worse than the best known for the integral problem in the popular random order model. We show that there is an algorithm for the online fractional knapsack problem that admits a competitive ratio of \(4.39\). Our result significantly improves over the previously best known competitive ratio of \(9.37\) and surpasses the current best \(6.65\)-competitive algorithm for the integral case. Moreover, our algorithm is deterministic in contrast to the randomized algorithms achieving the results mentioned above.

J. Giliberti—The work was carried out during a virtual internship at MPI for Informatics.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 6634
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 8293
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Items whose size exceeds the capacity of the knapsack can be cut at the knapsack capacity.

  2. 2.

    It can be accomplished in polynomial time by fixing a random (but consistent) tie-breaking between elements of the same value, based for instance on the identifier of the element [5].

References

  1. 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

  2. Albers, S., Ladewig, L.: New results for the k-secretary problem. Theor. Comput. Sci. 863, 102–119 (2021). https://doi.org/10.1016/j.tcs.2021.02.022

    Article  MathSciNet  MATH  Google Scholar 

  3. Babaioff, M., Hartline, J., Kleinberg, R.: Selling banner ads: Online algorithms with buyback. In: Fourth Workshop on Ad Auctions (2008)

    Google Scholar 

  4. 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–70 (2009)

    Google Scholar 

  5. 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–28. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74208-1_2

    Chapter  Google Scholar 

  6. Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM (JACM) 65(6), 1–26 (2018)

    Article  MathSciNet  Google Scholar 

  7. Böckenhauer, H.J., Burjons, E., Hromkovič, J., Lotze, H., Rossmanith, P.: Online simple knapsack with reservation costs. In: Bläser, 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–16:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2021). https://doi.org/10.4230/LIPIcs.STACS.2021.16

  8. 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–701. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_61

    Chapter  MATH  Google Scholar 

  9. 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–304. IEEE (2006)

    Google Scholar 

  10. Böckenhauer, H.J., Komm, D., Králvič, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci. 527, 61–72 (2014). https://doi.org/10.1016/j.tcs.2014.01.027

  11. 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–1188. https://doi.org/10.1137/1.9781611973730.78

  12. Dean, B.C., Goemans, M.X., Vondrák, J.: Adaptivity and approximation for stochastic packing problems. In: SODA, vol. 5, pp. 395–404. Citeseer (2005)

    Google Scholar 

  13. Dean, B.C., Goemans, M.X., Vondrák, J.: Approximating the stochastic knapsackproblem: the benefit of adaptivity. Math. Oper. Res.33(4), 945–964 (2008). https://doi.org/10.1287/moor.1080.0330

  14. Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Math. 4, 627–629 (1963)

    MATH  Google Scholar 

  15. 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–1201. SIAM (2014)

    Google Scholar 

  16. Goerigk, M., Gupta, M., Ide, J., Schöbel, A., Sen, S.: The robust knapsack problem with queries. Comput. Oper. Res. 55, 12–22 (2015). https://doi.org/10.1016/j.cor.2014.09.010

  17. Han, X., Kawase, Y., Makino, K.: Online unweighted knapsack problem with removal cost. Algorithmica 70(1), 76–91 (2014)

    Article  MathSciNet  Google Scholar 

  18. Han, X., Kawase, Y., Makino, K.: Randomized algorithms for online knapsack problems. Theor. Comput. Sci. 562, 395–405 (2015)

    Article  MathSciNet  Google Scholar 

  19. 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–28:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). https://doi.org/10.4230/LIPIcs.ISAAC.2019.28

  20. 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–305. Springer, Berlin Heidelberg, Berlin, Heidelberg (2002)

    Chapter  Google Scholar 

  21. Karrenbauer, A., Kovalevskaya, E.: Reading articles online. In: Wu, W., Zhang, Z. (eds.) COCOA 2020. LNCS, vol. 12577, pp. 639–654. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64843-5_43

    Chapter  Google Scholar 

  22. 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–72:15. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). https://doi.org/10.4230/LIPIcs.ICALP.2020.72

  23. Kesselheim, T., Radke, K., Tönnis, A., Vöcking, 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–600. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40450-4_50

    Chapter  Google Scholar 

  24. Kesselheim, T., Tönnis, A., Radke, K., Vöcking, 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–312. Association for Computing Machinery, New York (2014). https://doi.org/10.1145/2591796.2591810

  25. 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–631. Society for Industrial and Applied Mathematics, USA (2005)

    Google Scholar 

  26. Lindley, D.V.: Dynamic programming and decision theory. J. Roy. Stat. Soc. Ser. C (Appl. Stat.) 10(1), 39–51 (1961)

    MathSciNet  MATH  Google Scholar 

  27. Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2), 277–305 (1998). https://doi.org/10.1006/jagm.1998.0954

    Article  MathSciNet  MATH  Google Scholar 

  28. Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68(1), 73–104 (1995). https://doi.org/10.1007/BF01585758

  29. Marchetti-Spaccamela, A., Vercellis, C.: Stochastic on-line knapsack problems. Math. Program. 68(1), 73–104 (1995)

    MathSciNet  MATH  Google Scholar 

  30. 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–112. IEEE Computer Society, Los Alamitos, CA, USA, December 2005. https://doi.org/10.1109/ISPAN.2005.19

  31. 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

  32. Vaze, R.: Online knapsack problem under expected capacity constraint. In: IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pp. 2159–2167. IEEE (2018)

    Google Scholar 

  33. Vaze, R., Coupechoux, M.: Online budgeted truthful matching. SIGMETRICS Perform. Eval. Rev. 44(3), 3–6 (2017). https://doi.org/10.1145/3040230.3040232

    Article  Google Scholar 

  34. 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–576. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92185-1_63

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ETH Zurich, Zürich, Switzerland

    Jeff Giliberti

  2. MPI for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

    Jeff Giliberti & Andreas Karrenbauer

Authors
  1. Jeff Giliberti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andreas Karrenbauer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeff Giliberti .

Editor information

Editors and Affiliations

  1. University of Waterloo, Waterloo, ON, Canada

    Jochen Koenemann

  2. RWTH Aachen University, Aachen, Germany

    Britta Peis

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Giliberti, J., Karrenbauer, A. (2021). Improved Online Algorithm for Fractional Knapsack in the Random Order Model. In: Koenemann, J., Peis, B. (eds) Approximation and Online Algorithms. WAOA 2021. Lecture Notes in Computer Science(), vol 12982. Springer, Cham. https://doi.org/10.1007/978-3-030-92702-8_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92702-8_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92701-1

  • Online ISBN: 978-3-030-92702-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics