Document Open Access Logo

General Knapsack Problems in a Dynamic Setting

Authors Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, Danny Raz

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.15.pdf
  • Filesize: 0.69 MB
  • 18 pages

Document Identifiers

Author Details

Yaron Fairstein
  • Computer Science Department, Technion, Haifa, Israel
Ariel Kulik
  • Computer Science Department, Technion, Haifa, Israel
Joseph (Seffi) Naor
  • Computer Science Department, Technion, Haifa, Israel
Danny Raz
  • Computer Science Department, Technion, Haifa, Israel

Cite AsGet BibTex

Yaron Fairstein, Ariel Kulik, Joseph (Seffi) Naor, and Danny Raz. General Knapsack Problems in a Dynamic Setting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.15

Abstract

The world is dynamic and changes over time, thus any optimization problem used to model real life problems must address this dynamic nature, taking into account the cost of changes to a solution over time. The multistage model was introduced with this goal in mind. In this model we are given a series of instances of an optimization problem, corresponding to different times, and a solution is provided for each instance. The strive for obtaining near-optimal solutions for each instance on one hand, while maintaining similar solutions for consecutive time units on the other hand, is quantified and integrated into the objective function. In this paper we consider the Generalized Multistage d-Knapsack problem, a generalization of the multistage variants of the Multiple Knapsack problem, as well as the d-Dimensional Knapsack problem. We present a PTAS for Generalized Multistage d-Knapsack.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Multistage
  • Multiple-Knapsacks
  • Multidimensional Knapsack

Metrics

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

Related Versions

References

  1. Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Transactions on Algorithms (TALG), 13(2):1-20, 2017. Google Scholar
  2. Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th Paschos. Multistage matchings. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101, pages 7-1, 2018. Google Scholar
  3. Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online multistage subset maximization problems. In European Symposium on Algorithms (ESA), volume 144. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  4. Evripidis Bampis, Bruno Escoffier, and Alexandre Teiller. Multistage knapsack. In Mathematical Foundations of Computer Science (MFCS), volume 138, pages 22-1. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  5. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a submodular set function subject to a matroid constraint. In International Conference on Integer Programming and Combinatorial Optimization, pages 182-196. Springer, 2007. Google Scholar
  6. Chandra Chekuri and Sanjeev Khanna. On multidimensional packing problems. SIAM journal on computing, 33(4):837-851, 2004. Google Scholar
  7. Markus Chimani, Niklas Troost, and Tilo Wiedera. Approximating multistage matching problems. arXiv preprint arXiv:2002.06887, 2020. Google Scholar
  8. Shichuan Deng, Jian Li, and Yuval Rabani. Approximation algorithms for clustering with dynamic points. In 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  9. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In International Colloquium on Automata, Languages, and Programming, pages 459-470. Springer, 2014. Google Scholar
  10. Yaron Fairstein, Ariel Kulik, Danny Raz, et al. General knapsack problems in a dynamic setting. arXiv preprint arXiv:2105.00882, 2021. Google Scholar
  11. Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. Modular and submodular optimization with multiple knapsack constraints via fractional grouping. In 29th Annual European Symposium on Algorithms (ESA 2021), 2021. (To appear). Google Scholar
  12. Yaron Fairstein, Seffi Joseph Naor, and Danny Raz. Algorithms for dynamic nfv workload. In International Workshop on Approximation and Online Algorithms, pages 238-258. Springer, 2018. Google Scholar
  13. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634-652, 1998. Google Scholar
  14. Uriel Feige and Michel Goemans. Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In Proceedings Third Israel Symposium on the Theory of Computing and Systems, pages 182-189. IEEE, 1995. Google Scholar
  15. Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage vertex cover. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  16. Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche. Multistage st path: Confronting similarity with dissimilarity in temporal graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  17. Fabrizio Grandoni and Rico Zenklusen. Approximation schemes for multi-budgeted independence systems. In European Symposium on Algorithms, pages 536-548. Springer, 2010. Google Scholar
  18. Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for matroids and matchings. In International Colloquium on Automata, Languages, and Programming, pages 563-575. Springer, 2014. Google Scholar
  19. Ariel Kulik and Hadas Shachnai. There is no eptas for two-dimensional knapsack. Information Processing Letters, 110(16):707-710, 2010. Google Scholar
  20. George L Nemhauser and Laurence A Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3(3):177-188, 1978. Google Scholar
  21. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  22. Vijay V Vazirani. Approximation algorithms. Springer Science & Business Media, 2013. 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