Search

Bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k ≥ 2 , items having sizes in (0 , 1 ] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem and prove a lower bound of 2 on the overall asymptotic competitive ratio. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, where no such lower bound was known even for fixed high dimensions. [ABSTRACT FROM AUTHOR]

Abstract We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal. [ABSTRACT FROM AUTHOR]

We define and study a variant of bin packing called unrestricted black and white bin packing . Similarly to standard bin packing, a set of items of sizes in [ 0 , 1 ] are to be partitioned into subsets of total size at most 1, called bins. Items are of two types, called black and white, and the item types must alternate in each bin, that is, two items of the same type cannot be assigned consecutively into a bin. Thus, a subset of items of total size at most 1 can form a valid bin if and only if the absolute value of the difference between the numbers of black items and white items in the subset is at most 1. We study this problem both with respect to the absolute and the asymptotic approximation ratios. We design a fast heuristic whose absolute approximation ratio is 2. We also design an APTAS and modify it into an AFPTAS. The APTAS can be used as an algorithm of absolute approximation ratio 3 2 , which is the best possible absolute approximation ratio for the problem unless P = NP . [ABSTRACT FROM AUTHOR]

Abstract: On-line algorithms have been extensively studied for the one-dimensional bin packing problem. In this paper, we investigate two classes of one-dimensional bin packing algorithms, and we give better lower bounds for their asymptotic worst-case behavior. For on-line algorithms so far the best lower bound was given by van Vliet in (1992) . He proved that there is no on-line bin packing algorithm with better asymptotic performance ratio than 1.54014…. In this paper, we give an improvement on this bound to and we investigate the parametric case as well. For those lists where the elements are preprocessed according to their sizes in non-increasing order, Csirik et al. (1983)  proved that no on-line algorithm can have an asymptotic performance ratio smaller than . We improve this result to . [Copyright &y& Elsevier]

In 1996 Ivkovič and Lloyd [A fundamental restriction on fully dynamic maintenance of bin packing, Inform. Process. Lett., 59 (1996), pp. 229-232] gave the lower bound 4/3 on the asymptotic worst-case ratio for so-called fully dynamic bin packing algorithms, where the number of repackable items in each step is restricted by a constant. In this paper we improve this result to about 1.3871. We present our proof for a semionline case of the classical bin packing, but it works for fully dynamic bin packing as well. We prove the lower bound by analyzing and solving a specific optimization problem. The bound can be expressed exactly using the Lambert W function. [ABSTRACT FROM AUTHOR]