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...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2016
|
| Sorozat: | DISCRETE OPTIMIZATION
21 |
| Tárgyszavak: | |
| doi: | 10.1016/j.disopt.2016.04.007 |
| mtmt: | 3076539 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/28449 |
| Tartalmi kivonat: | 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. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 14-24 |
| ISSN: | 1572-5286 |