|
|||||
|
|
Improved lower bounds for semi-online bin packing problems |
|
| Authors: | János Balogh József Békési Gábor Galambos Mihály Csaba Markót |
| Affiliation: | 1. Department of Informatics’ Applications, Gyula Juhász Faculty of Education, University of Szeged, Boldogasszony sgt. 6, 6725, Szeged, Hungary 2. Advanced Concepts Team, European Space Agency, ESTEC, Noordwijk, The Netherlands 3. Faculty of Mathematics, University of Vienna, Nordbergstr. 15, 1090, Vienna, Austria |
| Abstract: | In the paper we deal with lower bounds constructed for the asymptotic competitive ratio of semi-online bin packing and batched bin packing algorithms.We determine the bounds as the solutions of a related nonlinear optimization problem using theoretical analysis and a reliable numerical global optimization method. Our results improve the lower bounds given in Gutin et al. (Discrete Optim 2:71–82, 2005) for some special cases of the batched bin packing problem. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |