Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Fully dynamic bin packing revisited
 
research article

Fully dynamic bin packing revisited

Berndt, Sebastian
•
Jansen, Klaus
•
Klein, Kim-Manuel  
January 1, 2020
Mathematical Programming

We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is the migration factor, defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio of 1+epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 + \epsilon $$\end{document} for the number of bins, a relatively simple argument proves a lower bound of omega(1/epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega ({1}/{\epsilon })$$\end{document} for the migration factor. We establish a nearly matching upper bound of O(1/epsilon 4log1/epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({1}/{\epsilon }<^>4 \log {1}/{\epsilon })$$\end{document} using a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of items nand in 1/epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${1}/{\epsilon }$$\end{document}. The previous best trade-off was for an asymptotic competitive ratio of 5/4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${5}/{4}$$\end{document} for the bins (rather than 1+epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1+\epsilon $$\end{document}) and needed an amortized number of O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document} repackings (while in our scheme the number of repackings is independent of n and non-amortized).

  • Details
  • Metrics
Type
research article
DOI
10.1007/s10107-018-1325-x
Web of Science ID

WOS:000526029200005

Author(s)
Berndt, Sebastian
Jansen, Klaus
Klein, Kim-Manuel  
Date Issued

2020-01-01

Publisher

SPRINGER HEIDELBERG

Published in
Mathematical Programming
Volume

179

Issue

1-2

Start page

109

End page

155

Subjects

Computer Science, Software Engineering

•

Operations Research & Management Science

•

Mathematics, Applied

•

Computer Science

•

Mathematics

•

primary: 68w27 (online algorithms)

•

secondary: 68w25 (approximation algorithms)

•

approximation schemes

•

algorithms

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
May 9, 2020
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/168656
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés