Lower bounds for batched bin packing

Autor:	József Békési, János Balogh, György Dósa, Leah Epstein, Asaf Levin
Rok vydání:	2021
Předmět:	Combinatorics Control and Optimization Computational Theory and Mathematics Bin packing problem Applied Mathematics Theory of computation Discrete Mathematics and Combinatorics Constant (mathematics) Mathematical proof Computer Science Applications Mathematics Parametric statistics
Zdroj:	Journal of Combinatorial Optimization. 43:613-629
ISSN:	1573-2886 1382-6905
Popis:	We consider batched bin packing. Items are presented in a constant number of batches, and each batch should be packed before the next batch is presented. The cases of two, three, and four batches are studied. We prove improved lower bounds for the standard and parametric variants in some of the cases, and shorten the proofs for all other cases. To achieve this, we apply a new technique in our analysis, which differs from the ones previously used for proving such results.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::9a8e4155adf0bf75b3e5b4e95d4ef4a4 https://doi.org/10.1007/s10878-021-00797-z Zobrazit plný text záznamu Full text from SpringerLink