TY - GEN
T1 - Fully-dynamic bin packing with little repacking
AU - Feldkord, Björn
AU - Feldotto, Matthias
AU - Gupta, Anupam
AU - Guruganesh, Guru
AU - Kumar, Amit
AU - Riechers, Sören
AU - Wajc, David
N1 - Publisher Copyright:
© Björn Feldkord, Matthias Feldotto, Anupam Gupta, Guru Guruganesh, Amit Kumar.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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.
AB - 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.
KW - Bin Packing
KW - Fully Dynamic
KW - Recourse
KW - Tradeoffs
UR - http://www.scopus.com/inward/record.url?scp=85049779645&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049779645&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.51
DO - 10.4230/LIPIcs.ICALP.2018.51
M3 - Conference contribution
AN - SCOPUS:85049779645
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Y2 - 9 July 2018 through 13 July 2018
ER -