Tight Bounds for Clairvoyant Dynamic Bin Packing
Authors:
Open Access
- 24 July 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 77-86
Abstract
In this paper we focus on the Clairvoyant Dynamic Bin Packing (DBP) problem, which extends the classical online bin packing problem in that items arrive and depart over time and the departure time of an item is known upon its arrival. The problem naturally arises when handling cloud-based networks. We focus specifically on the MinUsageTime cost function which aims to minimize the overall usage time of all bins that are opened during the packing process. Earlier work has shown a O(\frac{\log \mu}{\log \log \mu}) upper bound where \mu is defined as the ratio between the maximal and minimal durations of all items. We improve the upper bound by giving an O(\sqrt{\log \mu})-competitive algorithm. We then provide a matching lower bound of \Omega(\sqrt{\log \mu}) on the competitive ratio of any online algorithm, thus closing the gap with regards to this problem. We then focus on what we call the class of aligned inputs and give a O(\log \log \mu)-competitive algorithm for this case, beating the lower bound of the general case by an exponential factor. Surprisingly enough, the analysis of our algorithm that we present, is closely related to various properties of binary strings.Keywords
Funding Information
- Israel Science Foundation (1506/16)
- Blavatnik Fund
- Israeli Centers for Research Excellence (4/11)
This publication has 13 references indexed in Scilit:
- Play Request Dispatching for Efficient Virtual Machine Usage in Cloud GamingIEEE Transactions on Circuits and Systems for Video Technology, 2015
- Dynamic Bin Packing for On-Demand Cloud Resource AllocationIEEE Transactions on Parallel and Distributed Systems, 2015
- Online optimization of busy time on parallel machinesTheoretical Computer Science, 2014
- New lower bounds for certain classes of bin packing algorithmsTheoretical Computer Science, 2012
- An 8/3 Lower Bound for Online Dynamic Bin PackingLecture Notes in Computer Science, 2012
- On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation AnalysisAlgorithmica, 2008
- On the online bin packing problemJournal of the ACM, 2002
- An improved lower bound for on-line bin packing algorithmsInformation Processing Letters, 1992
- Dynamic Bin PackingSIAM Journal on Computing, 1983
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974