Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

An asymptotically exact algorithm for the high-multiplicity bin packing problem

The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C−2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly( log D)), where poly(·) is a polynomial function not depending on C.     

Selfish Square Packing

We consider a game-theoretical bin packing problem. The 1D (one dimensional) case has been treated in the literature as the ʼselfish bin packing problemʼ. We investigate a 2D version, in which the items to be packed are squares and the bins are unit squares. In this game, a set of items is packed into bins. Each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. One at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. At a Nash equilibrium, no player can reduce the cost he is charged by moving his item to a different bin. In the 2D case, to decide whether an item can be placed in another bin with other items is NP-complete, so we consider that players use a packing algorithm to make this decision. We show that this game converges to a Nash equilibrium, independently of the packing algorithm used. We prove that the price of anarchy is at least 2.27. We also prove that, using the NFDH packing algorithm, the asymptotic price of anarchy is at most 2.6875.     

On-line bin packing — A restricted survey

In the classical bin packing problem, one is asked to pack items of various sizes into the minimum number of equal-sized bins. In the on-line version of this problem, the packer is given the items one by one and must immediately and irrevocably assign every item to its bin, without knowing the future items. Beginning with the first results in the early 1970's, we survey — from the worst case point of view — the approximation results obtained for on-line bin packing, higher dimensional versions of the problem, lower bounds on worst case ratios and related results.This work was partially supported by the Christian Doppier Laboratorium für Diskrete Optimierung.     

The forgetfulness of balls and bins

We find the asymptotic total variation distance between two distributions on configurations of m balls in n labeled bins: in the first, each ball is placed in a bin uniformly at random; in the second, k balls are planted in an arbitrary but fixed arrangement and the remaining m ‐ k balls placed uniformly at random. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

On minimum k-modal partitions of permutations

Partitioning a permutation into a minimum number of monotone subsequences is -hard. We extend this complexity result to minimum partitioning into k-modal subsequences; here unimodal is the special case k=1. Based on a network flow interpretation we formulate both, the monotone and the k-modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k+1)-approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs.     

A stochastic analysis of the NFD bin-packing algorithm

We consider the Next-Fit-Decreasing (NFD) algorithm for the one-dimensional bin packing problem. The input consists of n pieces of i.i.d. sizes. Bounds on the first two moments of the number of bins used in the packing are established for arbitrary size distributions. These bounds are asymptotically tight. For the uniform distribution we also exhibit numerical results and examine their dependence on the support of the size distribution.     

On a dual version of the one-dimensional bin packing problem

The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of , , and the optimal number, at running time costs of O(n), O(nlogn), and O(nlog²n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items.     

The stochastic generalized bin packing problem

The Generalized Bin Packing Problem (GBPP) is a recently introduced packing problem where, given a set of bins characterized by volume and cost and a set of items characterized by volume and profit (which also depends on bins), we want to select a subset of items to be loaded into a subset of bins which maximizes the total net profit, while satisfying the volume and bin availability constraints. The total net profit is given by the difference between the total profit of the loaded items and the total cost of the used bins. In this paper, we consider the stochastic version of the GBPP (S-GBPP), where the item profits are random variables to take into account the profit oscillations due to the handling operations for bin loading. The probability distribution of these random variables is assumed to be unknown. By using the asymptotic theory of extreme values a deterministic approximation for the S-GBPP is derived.     

Average‐case analyses of first fit and random fit bin packing

We prove that the First Fit bin packing algorithm is stable under the input distribution U{k−2, k} for all k≥3, settling an open question from the recent survey by Coffman, Garey, and Johnson [“Approximation algorithms for bin backing: A survey,” Approximation algorithms for NP‐hard problems, D. Hochbaum (Editor), PWS, Boston, 1996]. Our proof generalizes the multidimensional Markov chain analysis used by Kenyon, Sinclair, and Rabani to prove that Best Fit is also stable under these distributions [Proc Seventh Annual ACM‐SIAM Symposium on Discrete Algorithms, 1995, pp. 351–358]. Our proof is motivated by an analysis of Random Fit, a new simple packing algorithm related to First Fit, that is interesting in its own right. We show that Random Fit is stable under the input distributions U{k−2, k}, as well as present worst case bounds and some results on distributions U{k−1, k} and U{k, k} for Random Fit. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 240–259, 2000     

A 7160 theorem for bin packing

The FIRST FIT DECREASING algorithm for bin packing has long been famous for its guarantee that no packing it generates will use more than $\text{11}\text{9}\text{= 1.222…}$ times the optimal number of bins. We present a simple modified version that has essentially the same running time, should perform at least as well on average, and yet provides a guarantee of $\text{71}\text{60}\text{= 1.18333…}$.     

Multiple-type,two-dimensional bin packing problems: Applications and algorithms

In this paper we consider a class of bin selection and packing problems (BPP) in which potential bins are of various types, have two resource constraints, and the resource requirement for each object differs for each bin type. The problem is to select bins and assign the objects to bins so as to minimize the sum of bin costs while meeting the two resource constraints. This problem represents an extension of the classical two-dimensional BPP in which bins are homogeneous. Typical applications of this research include computer storage device selection with file assignment, robot selection with work station assignment, and computer processor selection with task assignment. Three solution algorithms have been developed and tested: a simple greedy heuristic, a method based onsimulated annealing (SA) and an exact algorithm based onColumn Generation with Branch and Bound (CG). An LP-based method for generating tight lower bounds was also developed (LB). Several hundred test problems based on computer storage device selection and file assignment were generated and solved. The heuristic solved problems up to 100 objects in less than a second; average solution value was within about 3% of the optimum. SA improved solutions to an average gap of less than 1% but a significant increase in computing time. LB produced average lower bounds within 3% of optimum within a few seconds. CG is practical for small to moderately-sized problems — possibly as many as 50 objects.     

Bin packing: On optimizing the number of pieces packed

We consider bin-packing variations related to the well-studied problem of maximizing the total number of pieces packed into a fixed set of bins. We show that, when the objective is to minimize the total number of pieces packed subject to the constraint that no unpacked piece will fit, no polynomial-time relative approximation algorithm exists (unless, of course,P=NP). That is, we prove that it isNP-hard to guarantee packing no more than a constant multiple of the optimal number of pieces, for any constant. This appears to be the first bin-packing problem for which this property has been demonstrated. Furthermore, this result also holds for the allied packing variant which seeks to minimize the maximum number of pieces packed in any single bin. We find the situation to be markedly better for the problem of maximizing the minimum number of pieces in any bin. If all bins possess the same capacity, we prove that the familiar SPF rule is an absolute approximation algorithm with additive constant 1, and can therefore be regarded as a best possible heuristic. For the more general and difficult case in which bin capacities may differ, it turns out that SPF fails to qualify as even a relative approximation algorithm. However, we devise an implementation of the well-known FFD heuristic, which we show to be a relative approximation algorithm, yielding a worst-case performance ratio of 1/2 with additive constant 0. Moreover, we prove that (unlessP=NP) no polynomial-time algorithm can guarantee a higher ratio without sacrificing the additive constant.This author's research is supported in part by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

Relations between capacity utilization,minimal bin size and bin number

We consider the two-dimensional bin packing problem given a set of rectangular items, find the minimal number of rectangular bins needed to pack all items. Rotation of the items is not permitted. We show for any integer \({k} \ge 3\) that at most \({k}-1\) bins are needed to pack all items if every item fits into a bin and if the total area of items does not exceed \({k}/4\) -times the bin area. Moreover, this bound is tight. Furthermore, we show that only two bins are necessary to pack all items if the total area of items is not larger than the bin area, and if the height of each item is not larger than a third of the bin height and the width of every item does not exceed half of the bin width.     

Resource augmented semi-online bounded space bin packing

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308-320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.     

Next-fit packs a list and its reverse into the same number of bins

Suppose the next-fit algorithm packs {x₁, x₂, …, x_n} into k identical bins. Under modest assumptions about what fits into a bin, we prove that next-fit also packs {x_n, …, x₂, x₁} into k bins. Thus, the next-fit decreasing algorithm uses the same number of bins as a next-fit increasing algorithm.     

Three-dimensional bin packing problem with variable bin height

This paper studies a variant of the three-dimensional bin packing problem (3D-BPP), where the bin height can be adjusted to the cartons it packs. The bins and cartons to be packed are assumed rectangular in shape. The cartons are allowed to be rotated into any one of the six positions that keep the carton edges parallel to the bin edges. This greatly increases the difficulty of finding a good solution since the search space expands significantly comparing to the 3D-BPP where the cartons have fixed orientations. A mathematical (mixed integer programming) approach is modified based on [Chen, C. S., Lee, S. M., Shen, Q. S., 1995. An analytical model for the container loading problem. European Journal of Operational Research 80 (1), 68–76] and numerical experiments indicate that the mathematical approach is not suitable for the variable bin height 3D-BPP. A special bin packing algorithm based on packing index is designed to utilize the special problem feature and is used as a building block for a genetic algorithm designed for the 3D-BPP. The paper also investigates the situation where more than one type of bin are used and provides a heuristic for packing a batch of cartons using the genetic algorithm. Numerical experiments show that our proposed method yields quick and satisfactory results when benchmarked against the actual packing practice and the MIP model with the latest version of CPLEX.     

New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems

We consider two types of orthogonal, oriented, rectangular, two-dimensional packing problems. The first is the strip packing problem, for which four new and improved level-packing algorithms are presented. Two of these algorithms guarantee a packing that may be disentangled by guillotine cuts. These are combined with a two-stage heuristic designed to find a solution to the variable-sized bin packing problem, where the aim is to pack all items into bins so as to minimise the packing area. This heuristic packs the levels of a solution to the strip packing problem into large bins and then attempts to repack the items in those bins into smaller bins in order to reduce wasted space. The results of the algorithms are compared to those of seven level-packing heuristics from the literature by means of a large number of strip-packing benchmark instances. It is found that the new algorithms are an improvement over known level-packing heuristics for the strip packing problem. The advancements made by the new and improved algorithms are limited in terms of utilised space when applied to the variable-sized bin packing problem. However, they do provide results faster than many existing algorithms.     

Bin packing with general cost structures

Following the work of Anily et?al., we consider a variant of bin packing called bin packing with general cost structures (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously.