6 papers · 1 filter
Lower bounds on the performance of online algorithms for relaxed packing problems
János Balogh, György Dósa, Leah Epstein +1
We prove new lower bounds for suitable competitive ratio measures of two relaxed online packing problems: online removable multiple knapsack, and a recently introduced online minim…
More on ordered open end bin packing
János Balogh, Leah Epstein, Asaf Levin
We consider the Ordered Open End Bin Packing problem. Items of sizes in are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin f…
Truly asymptotic lower bounds for online vector bin packing
Janos Balogh, Leah Epstein, Asaf Levin
In this work, we consider online vector bin packing. It is known that no algorithm can have a competitive ratio of in the absolute sense, though upper bounds for th…
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…