Online Bin Covering with Limited Migration

Authors Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, Lars Rohwedder



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.18.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Sebastian Berndt
  • Department of Computer Science, Kiel University, Kiel, Germany
Leah Epstein
  • Department of Mathematics, University of Haifa, Haifa, Israel
Klaus Jansen
  • Department of Computer Science, Kiel University, Kiel, Germany
Asaf Levin
  • Faculty of Industrial Engineering and Management, The Technion, Haifa, Israel
Marten Maack
  • Department of Computer Science, Kiel University, Kiel, Germany
Lars Rohwedder
  • Department of Computer Science, Kiel University, Kiel, Germany

Acknowledgements

This work was partially supported by the DFG Project, "Robuste Online-Algorithmen für Scheduling- und Packungsprobleme", JA 612 /19-1, and by GIF-Project "Polynomial Migration for Online Scheduling".

Cite AsGet BibTex

Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder. Online Bin Covering with Limited Migration. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.18

Abstract

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most beta * s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classical problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small epsilon). We therefore resolve the competitiveness of the bin covering problem with migration.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithms
  • dynamic algorithms
  • competitive ratio
  • bin covering
  • migration factor

Metrics

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

References

  1. Susan F. Assmann, David S. Johnson, Daniel J. Kleitman, and Joseph Y.-T. Leung. On a Dual Version of the One-Dimensional Bin Packing Problem. J. Algorithms, 5(4):502-525, 1984. URL: https://doi.org/10.1016/0196-6774(84)90004-X.
  2. János Balogh, Leah Epstein, and Asaf Levin. Lower bounds for online bin covering-type problems. Journal of Scheduling, pages 1-11, 2018. Google Scholar
  3. Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein. Fully dynamic bin packing revisited. Mathematical Programming, 2018. URL: https://doi.org/10.1007/s10107-018-1325-x.
  4. Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen. Online bin covering: Expectations vs. guarantees. Theor. Comput. Sci., 556:71-84, 2014. URL: https://doi.org/10.1016/j.tcs.2014.06.029.
  5. János Csirik, David S. Johnson, and Claire Kenyon. Better approximation algorithms for bin covering. In S. Rao Kosaraju, editor, Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 557-566. ACM/SIAM, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365533.
  6. János Csirik and V. Totik. Online algorithms for a dual version of bin packing. Discrete Applied Mathematics, 21(2):163-167, 1988. URL: https://doi.org/10.1016/0166-218X(88)90052-2.
  7. Leah Epstein. Online Variable Sized Covering. Inf. Comput., 171(2):294-305, 2001. URL: https://doi.org/10.1006/inco.2001.3087.
  8. Leah Epstein, Lene M. Favrholdt, and Jens S. Kohrt. Comparing online algorithms for bin packing problems. J. Scheduling, 15(1):13-21, 2012. URL: https://doi.org/10.1007/s10951-009-0129-5.
  9. Leah Epstein, Csanád Imreh, and Asaf Levin. Class Constrained Bin Covering. Theory Comput. Syst., 46(2):246-260, 2010. URL: https://doi.org/10.1007/s00224-008-9129-7.
  10. Leah Epstein and Asaf Levin. A robust APTAS for the classical bin packing problem. Math. Program., 119(1):33-49, 2009. URL: https://doi.org/10.1007/s10107-007-0200-y.
  11. Leah Epstein and Asaf Levin. Robust Approximation Schemes for Cube Packing. SIAM Journal on Optimization, 23(2):1310-1343, 2013. URL: https://doi.org/10.1137/11082782X.
  12. Leah Epstein and Asaf Levin. Robust Algorithms for Preemptive Scheduling. Algorithmica, 69(1):26-57, 2014. URL: https://doi.org/10.1007/s00453-012-9718-3.
  13. 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 Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 51:1-51:24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.51.
  14. Carsten Fischer and Heiko Röglin. Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering. In Evangelos Kranakis, Gonzalo Navarro, and Edgar Chávez, editors, LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, volume 9644 of Lecture Notes in Computer Science, pages 469-482. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-49529-2_35.
  15. Carsten Fischer and Heiko Röglin. Probabilistic Analysis of Online (Class-Constrained) Bin Packing and Bin Covering. In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 461-474. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_34.
  16. Waldo Gálvez, José A. Soto, and José Verschae. Symmetry Exploitation for Online Machine Covering with Bounded Migration. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, volume 112 of LIPIcs, pages 32:1-32:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.32.
  17. Teofilo F. Gonzalez, editor. Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007. URL: https://doi.org/10.1201/9781420010749.
  18. Klaus Jansen and Kim-Manuel Klein. A Robust AFPTAS for Online Bin Packing with Polynomial Migration,. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 589-600. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_50.
  19. Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig. Online Strip Packing with Polynomial Migration. In Klaus Jansen, José D. P. Rolim, David Williamson, and Santosh Srinivas Vempala, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LIPIcs, pages 13:1-13:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.13.
  20. Klaus Jansen and Roberto Solis-Oba. An asymptotic fully polynomial time approximation scheme for bin covering. Theor. Comput. Sci., 306(1-3):543-551, 2003. URL: https://doi.org/10.1016/S0304-3975(03)00363-3.
  21. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online Scheduling with Bounded Migration. Math. Oper. Res., 34(2):481-498, 2009. URL: https://doi.org/10.1287/moor.1090.0381.
  22. 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. URL: https://doi.org/10.1287/moor.2015.0765.
  23. Gerhard J. Woeginger and Guochuan Zhang. Optimal on-line algorithms for variable-sized bin covering. Oper. Res. Lett., 25(1):47-50, 1999. URL: https://doi.org/10.1016/S0167-6377(99)00023-1.
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