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...

Full description

Saved in:
Bibliographic Details
Main Authors: Balogh János
Békési József
Galambos Gábor
Dósa György
Tan Zhiyi
Format: Article
Published: 2016
Series:DISCRETE OPTIMIZATION 21
Subjects:
doi:10.1016/j.disopt.2016.04.007

mtmt:3076539
Online Access:http://publicatio.bibl.u-szeged.hu/28449
Description
Summary: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.
Physical Description:14-24
ISSN:1572-5286