On data reduction for dynamic vector bin packing

Abstract

We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover $(1+\epsilon )$-approximate solutions for arbitrary $\epsilon >0$. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for $\epsilon =0.02$.

Version accepted to Operations Research Letters

References in corpus (1)

• A Branch-and-Price Algorithm for the Temporal Bin Packing Problem

Cited by in corpus (1)

• Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU