Document Open Access Logo

Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time

Authors Franziska Eberle , Nicole Megow , Lukas Nölke , Bertrand Simon , Andreas Wiese

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.18.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Franziska Eberle
  • Faculty of Mathematics and Computer Science, University of Bremen, Germany
Nicole Megow
  • Faculty of Mathematics and Computer Science, University of Bremen, Germany
Lukas Nölke
  • Faculty of Mathematics and Computer Science, University of Bremen, Germany
Bertrand Simon
  • IN2P3 Computing Center, CNRS, Villeurbanne, France
Andreas Wiese
  • Department of Industrial Engineering, University of Chile, Santiago, Chile

Funding

This work is partly funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project Number 146371743 - TRR 89 Invasive Computing.

Acknowledgements

We thank Martin Böhm, Peter Kling, and Jens Schlöter for the fruitful discussions.

Cite AsGet BibTex

Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon, and Andreas Wiese. Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.18

Abstract

Knapsack problems are among the most fundamental problems in optimization. In the Multiple Knapsack problem, we are given multiple knapsacks with different capacities and items with values and sizes. The task is to find a subset of items of maximum total value that can be packed into the knapsacks without exceeding the capacities. We investigate this problem and special cases thereof in the context of dynamic algorithms and design data structures that efficiently maintain near-optimal knapsack solutions for dynamically changing input. More precisely, we handle the arrival and departure of individual items or knapsacks during the execution of the algorithm with worst-case update time polylogarithmic in the number of items. As the optimal and any approximate solution may change drastically, we maintain implicit solutions and support polylogarithmic time query operations that can return the computed solution value and the packing of any given item. While dynamic algorithms are well-studied in the context of graph problems, there is hardly any work on packing problems (and generally much less on non-graph problems). Motivated by the theoretical interest in knapsack problems and their practical relevance, our work bridges this gap.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
Keywords
  • Fully dynamic algorithms
  • knapsack problem
  • approximation schemes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, and Barna Saha. Dynamic set cover: improved algorithms and lower bounds. In STOC, pages 114-125. ACM, 2019. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS, pages 434-443. IEEE Computer Society, 2014. Google Scholar
  3. Kyriakos Axiotis and Christos Tzamos. Capacitated dynamic programming: Faster knapsack and graph algorithms. In ICALP, volume 132 of LIPIcs, pages 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  4. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 382-405. IEEE, 2019. Google Scholar
  5. Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1957. Google Scholar
  6. Anton Beloglazov and Rajkumar Buyya. Energy efficient allocation of virtual machines in cloud data centers. In CCGRID, pages 577-578. IEEE Computer Society, 2010. Google Scholar
  7. Anand Bhalgat, Ashish Goel, and Sanjeev Khanna. Improved approximation results for stochastic knapsack problems. In SODA, pages 1647-1665. SIAM, 2011. Google Scholar
  8. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Design of dynamic algorithms via primal-dual method. In ICALP (1), volume 9134 of Lecture Notes in Computer Science, pages 206-218. Springer, 2015. Google Scholar
  9. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log^3 n) worst case update time. In SODA, pages 470-489. SIAM, 2017. Google Scholar
  10. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. A new deterministic algorithm for dynamic set cover. In FOCS, pages 406-423. IEEE Computer Society, 2019. Google Scholar
  11. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 + ε)-approximate minimum vertex cover in o(1/ε²) amortized update time. In SODA, pages 1872-1885. SIAM, 2019. Google Scholar
  12. Sujoy Bhore, Jean Cardinal, John Iacono, and Grigorios Koumoutsos. Dynamic geometric independent set. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.08643.
  13. Norman Bobroff, Andrzej Kochut, and Kirk A. Beaty. Dynamic placement of virtual machines for managing SLA violations. In Integrated Network Management, pages 119-128. IEEE, 2007. Google Scholar
  14. Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, and Peter Rossmanith. The online knapsack problem: Advice and randomization. Theor. Comput. Sci., 527:61-72, 2014. Google Scholar
  15. Nicolas Boria and Vangelis Th. Paschos. A survey on combinatorial optimization in dynamic environments. RAIRO - Operations Research, 45(3):241-294, 2011. Google Scholar
  16. Christina Büsing, Arie M. C. A. Koster, and Manuel Kutschka. Recoverable robust knapsacks: the discrete scenario case. Optim. Lett., 5(3):379-392, 2011. Google Scholar
  17. Timothy M. Chan. Approximation schemes for 0-1 knapsack. In SOSA@SODA, volume 61 of OASICS, pages 5:1-5:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  18. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In FOCS, pages 370-381. IEEE, 2019. Google Scholar
  19. Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput., 35(3):713-728, 2005. Google Scholar
  20. Spencer Compton, Slobodan Mitrović, and Ronitt Rubinfeld. New partitioning techniques and faster algorithms for approximate interval scheduling. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.15002.
  21. Marek Cygan, Łukasz Jeż, and Jiří Sgall. Online knapsack revisited. Theory Comput. Syst., 58(1):153-190, 2016. Google Scholar
  22. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. Google Scholar
  23. Khuzaima Daudjee, Shahin Kamali, and Alejandro López-Ortiz. On the online fault-tolerant server consolidation problem. In SPAA, pages 12-21. ACM, 2014. Google Scholar
  24. Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1+epsilon in linear time. Combinatorica, 1(4):349-355, 1981. Google Scholar
  25. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res., 33(4):945-964, 2008. Google Scholar
  26. Camil Demetrescu, David Eppstein, Zvi Galil, and Giuseppe F. Italiano. Dynamic Graph Algorithms, page 9. Chapman & Hall/CRC, 2 edition, 2010. Google Scholar
  27. Yann Disser, Max Klimm, Nicole Megow, and Sebastian Stiller. Packing a knapsack of unknown capacity. SIAM J. Discret. Math., 31(3):1477-1497, 2017. Google Scholar
  28. Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon, and Andreas Wiese. Fully dynamic algorithms for knapsack problems with polylogarithmic update time. CoRR, abs/2007.08415, 2020. URL: http://arxiv.org/abs/2007.08415.
  29. Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, and David Wajc. Fully-dynamic bin packing with little repacking. In ICALP, volume 107 of LIPIcs, pages 51:1-51:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  30. George Gens and Eugene Levner. Computational complexity of approximation algorithms for combinatorial problems. In MFCS, volume 74 of Lecture Notes in Computer Science, pages 292-300. Springer, 1979. Google Scholar
  31. George Gens and Eugene Levner. Fast approximation algorithms for knapsack type problems. In Optimization Techniques, pages 185-194. Springer, 1980. Google Scholar
  32. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  33. Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: Maintaining a constant-competitive steiner tree online. SIAM J. Comput., 45(1):1-28, 2016. Google Scholar
  34. Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi. Online and dynamic algorithms for set cover. In STOC, pages 537-550. ACM, 2017. Google Scholar
  35. Xin Han, Yasushi Kawase, and Kazuhisa Makino. Randomized algorithms for removable online knapsack problems. In FAW-AAIM, volume 7924 of Lecture Notes in Computer Science, pages 60-71. Springer, 2013. Google Scholar
  36. Xin Han, Yasushi Kawase, Kazuhisa Makino, and He Guo. Online removable knapsack problem under convex function. Theor. Comput. Sci., 540:62-69, 2014. Google Scholar
  37. Xin Han and Kazuhisa Makino. Online removable knapsack with limited cuts. Theor. Comput. Sci., 411(44-46):3956-3964, 2010. Google Scholar
  38. Monika Henzinger. The state of the art in dynamic graph algorithms. In SOFSEM, volume 10706 of Lecture Notes in Computer Science, pages 40-44. Springer, 2018. Google Scholar
  39. Monika Henzinger, Stefan Neumann, and Andreas Wiese. Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles. In SoCG, volume 164 of LIPIcs, pages 51:1-51:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.51.
  40. Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, 1999. Google Scholar
  41. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM, 34(1):144-162, 1987. Google Scholar
  42. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. Google Scholar
  43. Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM, 22(4):463-468, 1975. Google Scholar
  44. Makoto Imase and Bernard M. Waxman. Dynamic steiner tree problem. SIAM J. Discret. Math., 4(3):369-384, 1991. Google Scholar
  45. Zoran Ivkovic and Errol L. Lloyd. Fully dynamic algorithms for bin packing: Being (mostly) myopic helps. SIAM J. Comput., 28(2):574-611, 1998. Google Scholar
  46. Kazuo Iwama and Shiro Taketomi. Removable online knapsack problems. In ICALP, volume 2380 of Lecture Notes in Computer Science, pages 293-305. Springer, 2002. Google Scholar
  47. Kazuo Iwama and Guochuan Zhang. Online knapsack with resource augmentation. Inf. Process. Lett., 110(22):1016-1020, 2010. Google Scholar
  48. Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem. SIAM J. Comput., 39(4):1392-1412, 2009. Google Scholar
  49. Klaus Jansen. An EPTAS for scheduling jobs on uniform processors: Using an MILP relaxation with a constant number of integral variables. SIAM J. Discrete Math., 24(2):457-485, 2010. Google Scholar
  50. Klaus Jansen. A fast approximation scheme for the multiple knapsack problem. In SOFSEM, volume 7147 of Lecture Notes in Computer Science, pages 313-324. Springer, 2012. Google Scholar
  51. Klaus Jansen and Kim-Manuel Klein. A robust AFPTAS for online bin packing with polynomial migration. SIAM J. Discret. Math., 33(4):2062-2091, 2019. Google Scholar
  52. Ce Jin. An improved FPTAS for 0-1 knapsack. In ICALP, volume 132 of LIPIcs, pages 76:1-76:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  53. Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In FOCS, pages 312-320. IEEE Computer Society, 1982. Google Scholar
  54. Hans Kellerer. A polynomial time approximation scheme for the multiple knapsack problem. In RANDOM-APPROX, volume 1671 of Lecture Notes in Computer Science, pages 51-62. Springer, 1999. Google Scholar
  55. Hans Kellerer and Ulrich Pferschy. Improved dynamic programming in connection with an FPTAS for the knapsack problem. J. Comb. Optim., 8(1):5-11, 2004. Google Scholar
  56. Ariel Kulik and Hadas Shachnai. There is no EPTAS for two-dimensional knapsack. Inf. Process. Lett., 110(16):707-710, 2010. Google Scholar
  57. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In ICALP, volume 80 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  58. Eugene L. Lawler. Fast approximation algorithms for knapsack problems. Math. Oper. Res., 4(4):339-356, 1979. Google Scholar
  59. Yusen Li, Xueyan Tang, and Wentong Cai. On dynamic bin packing for resource allocation in the cloud. In SPAA, pages 2-11. ACM, 2014. Google Scholar
  60. Will Ma. Improvements and generalizations of stochastic knapsack and markovian bandits approximation algorithms. Math. Oper. Res., 43(3):789-812, 2018. Google Scholar
  61. Alberto Marchetti-Spaccamela and Carlo Vercellis. Stochastic on-line knapsack problems. Math. Program., 68:73-104, 1995. Google Scholar
  62. Nicole Megow and Julián Mestre. Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In ITCS, pages 495-504. ACM, 2013. Google Scholar
  63. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. SIAM J. Comput., 45(3):859-880, 2016. Google Scholar
  64. Morteza Monemizadeh. Dynamic maximal independent set. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.09595.
  65. Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. A subquadratic approximation scheme for partition. In SODA, pages 70-88. SIAM, 2019. Google Scholar
  66. Adam Polak, Lars Rohwedder, and Karol Wegrzycki. Knapsack and subset sum with small items. In ICALP, volume 198 of LIPIcs, pages 106:1-106:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  67. Donguk Rhee. Faster fully polynomial approximation schemes for knapsack problems. Master’s thesis, Massachusetts Institute of Technology, 2015. Google Scholar
  68. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Math. Oper. Res., 34(2):481-498, 2009. Google Scholar
  69. Martin Skutella and José Verschae. Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures. Math. Oper. Res., 41(3):991-1021, 2016. Google Scholar
  70. Gang Yu. On the max-min 0-1 knapsack problem with robust optimization applications. Oper. Res., 44(2):407-415, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact