Fully-dynamic bin packing with little repacking

Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar, Sören Riechers, David Wajc

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the classic bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. We want algorithms with low asymptotic competitive ratio while repacking items sparingly between updates. Formally, each item i has a movement cost ci ≥ 0, and we want to use α·OPT bins and incur a movement cost γ·ci, either in the worst case, or in an amortized sense, for α, γ as small as possible. We call γ the recourse of the algorithm. This is motivated by cloud storage applications, where fully-dynamic bin packing models the problem of data backup to minimize the number of disks used, as well as communication incurred in moving file backups between disks. Since the set of files changes over time, we could recompute a solution periodically from scratch, but this would give a high number of disk rewrites, incurring a high energy cost and possible wear and tear of the disks. In this work, we present optimal tradeo s between number of bins used and number of items repacked, as well as natural extensions of the latter measure.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Other

Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/TerritoryCzech Republic
CityPrague
Period7/9/187/13/18

Keywords

  • Bin Packing
  • Fully Dynamic
  • Recourse
  • Tradeoffs

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Fully-dynamic bin packing with little repacking'. Together they form a unique fingerprint.

Cite this