On data reduction for dynamic vector bin packing

DOI10.1016/J.ORL.2023.06.005MaRDI QIDQ6047700zbMATH OpenFDO

Authors René van Bevern, Andrey Melnikov, Pavel V. Smirnov, O. Yu. Tsidulko

Publication date 12 September 2023

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.08769

zbMATH Keywords

approximation \& heuristicslossy kernelizationparameterized complexityresource allocation

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Combinatorial optimization (90C27)

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+varepsilon)$-approximate solutions for arbitrary $varepsilon>0$. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for $varepsilon=0.02$.

Recommendations

• Sequential vector packing
• Packing small vectors
• Sequential Vector Packing
• Improved Approximation for Vector Bin Packing
• Tight bounds for online vector bin packing

Cites work

• A branch-and-price algorithm for the temporal bin packing problem
• Approximation and online algorithms for multidimensional bin packing: a survey
• Dynamic Bin Packing
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved Approximation for Vector Bin Packing
• Integer Programming with a Fixed Number of Variables
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• Lossy kernelization
• Minkowski's Convex Body Theorem and Integer Programming
• Parametrized complexity theory.
• Presolve Reductions in Mixed Integer Programming
• There is no asymptotic PTAS for two-dimensional vector packing

Cited in

(1)

• Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU

This page was built for publication: On data reduction for dynamic vector bin packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047700)