Lower bound for 3-batched bin packing

Lower bound for 3-batched bin packing

Abstract In this paper we will consider a special relaxation of the well-known online bin packing problem. In a batched bin packing problem (BBPP)–defined by Gutin et al. (2005)–the elements come in batches and one batch is available for packing in a given time. If we have K ≥ 2 batches then we deno...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerzők: Balogh János
Békési József
Galambos Gábor
Dósa György
Tan Zhiyi
Dokumentumtípus: Cikk
Megjelent: 2016
Sorozat:DISCRETE OPTIMIZATION 21
Tárgyszavak:
Számítás- és információtudomány
doi:10.1016/j.disopt.2016.04.007

mtmt:3076539
Online Access:http://publicatio.bibl.u-szeged.hu/28449
LEADER 01394nab a2200265 i 4500
001 publ28449
005 20231017144602.0
008 231017s2016 hu o 0|| Angol d
022 |a 1572-5286 
024 7 |a 10.1016/j.disopt.2016.04.007  |2 doi 
024 7 |a 3076539  |2 mtmt 
040 |a SZTE Publicatio Repozitórium  |b hun 
041 |a Angol 
100 1 |a Balogh János 
245 1 0 |a Lower bound for 3-batched bin packing  |h [elektronikus dokumentum] /  |c  Balogh János 
260 |c 2016 
300 |a 14-24 
490 0 |a DISCRETE OPTIMIZATION  |v 21 
520 3 |a Abstract In this paper we will consider a special relaxation of the well-known online bin packing problem. In a batched bin packing problem (BBPP)–defined by Gutin et al. (2005)–the elements come in batches and one batch is available for packing in a given time. If we have K ≥ 2 batches then we denote the problem by K -BBPP. In Gutin et al. (2005) the authors gave a 1.3871 … lower bound for the asymptotic competitive ratio (ACR) of any on-line 2 -BBBP algorithm. In this paper we investigate the 3-BBPP, and we give 1.51211 … lower bound for its ACR. 
650 4 |a Számítás- és információtudomány 
700 0 1 |a Békési József  |e aut 
700 0 1 |a Galambos Gábor  |e aut 
700 0 1 |a Dósa György  |e aut 
700 0 1 |a Tan Zhiyi  |e aut 
856 4 0 |u http://publicatio.bibl.u-szeged.hu/28449/1/3batch.pdf  |z Dokumentum-elérés  

Hasonló tételek