5 papers
Joint replenishment meets scheduling
Péter Györgyi, Tamás Kis, Tímea Tamási +1
In this paper we consider a combination of the joint replenishment problem (JRP) and single machine scheduling with release dates. There is a single machine and one or more item ty…
A new lower bound for classic online bin packing
János Balogh, József Békési, György Dósa +2
We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branchin…
Lower bounds for several online variants of bin packing
János Balogh, József Békési, György Dósa +2
We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a meth…
A new and improved algorithm for online bin packing
János Balogh, József Békési, György Dósa +2
We revisit the classic online bin packing problem. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called "bins" of tot…
Online bin packing with cardinality constraints resolved
János Balogh, József Békési, György Dósa +2
Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k \geq 2, items having size…