On data reduction for dynamic vector bin packing

Autor:	van Bevern, René, Melnikov, Andrey, Smirnov, Pavel, Tsidulko, Oxana
Rok vydání:	2022
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics Mathematics - Optimization and Control
Zdroj:	Operations Research Letters 51:446-452, 2023
Druh dokumentu:	Working Paper
DOI:	10.1016/j.orl.2023.06.005
Popis:	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$. Comment: Version accepted to Operations Research Letters
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2205.08769 Zobrazit plný text záznamu View this record from Arxiv