We consider robust variants of the bin packing problem with uncertain item sizes. Specifically we consider two uncertainty sets previously studied in the literature. The first is budgeted uncertainty (the $U^\Gamma$ model), in which at most $\Gamma$ items deviate, each reaching its peak value, while other items assume their nominal values. The second uncertainty set, the $U^\Omega$ model, bounds the total amount of deviation in each scenario. We show that a variant of the Next-cover algorithm is a $2$ approximation for the $U^\Omega$ model, and another variant of this algorithm is a $2\Gamma$ approximation for the $U^\Gamma$ model. Unlike the classical bin packing problem, it is shown that (unless $\mathcal{P}=\mathcal{NP}$) no asymptotic approximation scheme exists for the $U^\Gamma$ model, for $\Gamma=1$. This motivates the question of the existence of a constant approximation factor algorithm for the $U^\Gamma$ model. Our main result is to answer this question by proving a (polynomial-time) $4.5$ approximation algorithm, based on a dynamic-programming approach.

We consider the scheduling model with two identical machines and jobs which arrive online in a list and are assigned to the machines with the objective of minimizing the makespan. Differently from the pure online version, we know in advance a lower bound and also an upper bound on the total size of all jobs. Our algorithm improves previous results on some interval of r, where r is the ratio of the upper and lower bounds on the total size. For most ranges of r our algorithm is best possible. Our technique is based on a smart application of so-called “safe sets”.

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.

We consider several previously studied online variants of bin packing and prove new and improved lower bounds on the asymptotic competitive ratios for them. For that, we use a method of fully adaptive constructions. In particular, we improve the lower bound for the asymptotic competitive ratio of online square packing significantly, raising it from roughly 1.68 to above 1.75.

We revisit the classic online bin packing problem. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called "bins" of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier and provide an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.5783.

Cardinality constrained bin packing or 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 in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k is known. 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. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.

We present an online bin packing algorithm with absolute competitive ratio 5/3, which is optimal.

In the bin packing problem we are given an instance consisting of a sequence of items with sizes between 0 and 1. The objective is to pack these items into the smallest possible number of bins of unit size. FirstFit algorithm packs each item into the first bin where it fits, possibly opening a new bin if the item cannot fit into any currently open bin. In early seventies it was shown that the asymptotic approximation ratio of FirstFit bin packing is equal to 1.7. We prove that also the absolute approximation ratio for FirstFit bin packing is exactly 1.7. This means that if the optimum needs OPT bins, FirstFit always uses at most \lfloor 1.7 OPT \rfloor bins. Furthermore we show matching lower bounds for a majority of values of OPT, i.e., we give instances on which FirstFit uses exactly \lfloor 1.7 OPT \rfloor bins. Such matching upper and lower bounds were previously known only for finitely many small values of OPT. The previous published bound on the absolute approximation ratio of FirstFit was 12/7 \approx 1.7143. Recently a bound of 101/59 \approx 1.7119 was claimed.

We consider online preemptive scheduling of jobs, arriving one by one, on m identical parallel machines. A buffer of a fixed size $K>0$, which assists in partial reordering of the input, is available to be used for the storage of at most K unscheduled jobs. We study the effect of using a fixed-size buffer (of an arbitrary size) on the supremum competitive ratio over all numbers of machines (the overall competitive ratio), as well as the effect on the competitive ratio as a function of m. We find a tight bound on the competitive ratio for any m. This bound is $\frac{4}{3}$ for even values of m and slightly lower for odd values of m. We show that a buffer of size $\Theta(m)$ is sufficient to achieve this bound, but using $K=o(m)$ does not reduce the best overall competitive ratio that is known for the case without reordering, $\frac{e}{e-1}$. We further consider the semionline variant where jobs arrive sorted by nonincreasing processing time requirements. In this case it turns out to be possible to achieve a competitive ratio of 1. In addition, we find tight bounds as a function of the buffer size and the number of machines for this semionline variant. Related results for nonpreemptive scheduling were recently obtained by Englert, Özmen, and Westermann.

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently Imreh and Noga proposed adding the concept of machine cost to scheduling problems and considered the so-called list model problem. For this problem, we are given a sequence of independent jobs with positive sizes, which must be processed nonpreemptively on a machine. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. The objective is to minimize the sum of the makespan and cost of machines. In this paper, we first present an online algorithm with a competitive ratio at most 1.5798, which improves the known upper bound 1.618. Then for a special case where every job size is no greater than the machine cost, we present an optimal online algorithm with a competitive ratio 4/3. Last, we present an algorithm with a competitive ratio at most 3/2 for the semionline problem with known largest size, which improves the known upper bound 1.5309.