Document Open Access Logo

Online Strip Packing with Polynomial Migration

Authors Klaus Jansen, Kim-Manuel Klein, Maria Kosche, Leon Ladewig

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.13.pdf
  • Filesize: 0.97 MB
  • 18 pages

Document Identifiers

Author Details

Klaus Jansen
Kim-Manuel Klein
Maria Kosche
Leon Ladewig

Cite AsGet BibTex

Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig. Online Strip Packing with Polynomial Migration. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.13

Abstract

We consider the relaxed online strip packing problem, where rectangular items arrive online and have to be packed into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1 + O(epsilon) for any epsilon > 0 and amortized migration factor polynomial in 1/epsilon. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.
Keywords
  • strip packing
  • bin packing
  • online algorithms
  • migration factor

Metrics

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

References

  1. Brenda S. Baker, Edward G. Coffman, Jr, and Ronald L. Rivest. Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4):846-855, 1980. Google Scholar
  2. Brenda S. Baker and Jerald S. Schwarz. Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing, 12(3):508-525, 1983. Google Scholar
  3. János Balogh, József Békési, and Gábor Galambos. New lower bounds for certain classes of bin packing algorithms. Theoretical Computer Science, 440:1-13, 2012. Google Scholar
  4. Sebastian Berndt, Klaus Jansen, and Kim-Manuel Klein. Fully dynamic bin packing revisited. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 135-151, 2015. Google Scholar
  5. Donna J. Brown, Brenda S. Baker, and Howard P. Katseff. Lower bounds for on-line two-dimensional packing algorithms. Acta Informatica, 18(2):207-225, 1982. Google Scholar
  6. Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, and Prasad Tetali. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review, 2017. Google Scholar
  7. Edward G. Coffman, Jr, Michael R. Garey, David S. Johnson, and Robert E. Tarjan. Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4):808-826, 1980. Google Scholar
  8. János Csirik and Gerhard J. Woeginger. Shelf algorithms for on-line strip packing. Information Processing Letters, 63(4):171-175, 1997. Google Scholar
  9. Kurt Eisemann. The trim problem. Management Science, 3(3):279-284, 1957. Google Scholar
  10. Leah Epstein and Asaf Levin. A robust APTAS for the classical bin packing problem. Mathematical Programming, 119(1):33-49, 2009. Google Scholar
  11. Giorgio Gambosi, Alberto Postiglione, and Maurizio Talamo. Algorithms for the relaxed online bin-packing model. SIAM Journal on Computing, 30(5):1532-1551, 2000. Google Scholar
  12. Xin Han, Kazuo Iwama, Deshi Ye, and Guochuan Zhang. Strip packing vs. bin packing. In International Conference on Algorithmic Applications in Management (AAIM), pages 358-367. Springer, 2007. Google Scholar
  13. Rolf Harren, Klaus Jansen, Lars Prädel, and Rob Van Stee. A (5/3+ ε)-approximation for strip packing. Computational Geometry, 47(2):248-267, 2014. Google Scholar
  14. Johann L. Hurink and Jacob J. Paulus. Online algorithm for parallel job scheduling and strip packing. In International Workshop on Approximation and Online Algorithms (WAOA), pages 67-74. Springer, 2007. Google Scholar
  15. Johann L. Hurink and Jacob J. Paulus. Online scheduling of parallel jobs on two machines is 2-competitive. Operations Research Letters, 36(1):51-56, 2008. Google Scholar
  16. Csanád Imreh. Online strip packing with modifiable boxes. Operations Research Letters, 29(2):79-85, 2001. Google Scholar
  17. Klaus Jansen and Kim-Manuel Klein. A robust AFPTAS for online bin packing with polynomial migration. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 589-600. Springer, 2013. Google Scholar
  18. Klaus Jansen, Kim-Manuel Klein, Maria Kosche, and Leon Ladewig. Online strip packing with polynomial migration. CoRR, abs/1706.04939, 2017. URL: http://arxiv.org/abs/1706.04939.
  19. Berit Johannes. Scheduling parallel jobs to minimize the makespan. Journal of Scheduling, 9(5):433-452, 2006. Google Scholar
  20. Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In Foundations of Computer Science (FOCS), pages 312-320, Nov 1982. Google Scholar
  21. Claire Kenyon and Eric Rémila. A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research, 25(4):645-656, 2000. Google Scholar
  22. Walter Kern and Jacob J. Paulus. A note on the lower bound for online strip packing. Statistics and Computing, 2009. Google Scholar
  23. Kirk Pruhs, Jiri Sgall, and Eric Torng. Online scheduling. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, pages 15-1, 2004. Google Scholar
  24. Peter Sanders, Naveen Sivadasan, and Martin Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Google Scholar
  25. Steven S. Seiden. On the online bin packing problem. Journal of the ACM (JACM), 49(5):640-671, 2002. Google Scholar
  26. Martin Skutella and José Verschae. Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures. Mathematics of Operations Research, 41(3):991-1021, 2016. Google Scholar
  27. Christoph Steiger, Herbert Walder, Marco Platzner, and Lothar Thiele. Online scheduling and placement of real-time tasks to partially reconfigurable devices. In Real-Time Systems Symposium, 2003. RTSS 2003. 24th IEEE, pages 224-225. IEEE, 2003. Google Scholar
  28. Deshi Ye, Xin Han, and Guochuan Zhang. A note on online strip packing. Journal of Combinatorial Optimization, 17(4):417-423, 2009. Google Scholar
  29. Deshi Ye, Xin Han, and Guochuan Zhang. Online multiple-strip packing. Theoretical Computer Science, 412(3):233-239, 2011. Google Scholar
  30. Guosong Yu, Yanling Mao, and Jiaoliao Xiao. A new lower bound for online strip packing. European Journal of Operational Research, 250(3):754-759, 2016. 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