Approximating Robust Bin Packing with Budgeted Uncertainty

Abstract

We consider robust variants of the bin-packing problem where the sizes of the items can take any value in a given uncertainty set $U\subseteq \times _{i=1}^n[\overline{a}_i,\overline{a}_i+\hat{a}_i]$, where $\overline{a}\in [0,1]^n$ represents the nominal sizes of the items and $\hat{a}\in [0,1]^n$ their possible deviations. We consider more specifically two uncertainty sets previously studied in the literature. The first set, denoted $U^\varGamma$, contains scenarios in which at most $\varGamma \in \mathbb {N}$ items deviate, each of them reaching its peak value $\overline{a}_i+\hat{a}_i$, while each other item has its nominal value $\overline{a}_i$. The second set, denoted $U^\varOmega$, bounds by $\varOmega \in [0,1]$ the total amount of deviation in each scenario. We show that a variant of the next-fit algorithm provides a 2-approximation for model $U^\varOmega$, and a $2(\varGamma +1)$ approximation for model $U^\varGamma$ (which can be improved to 2 approximation for $\varGamma =1$). This motivates the question of the existence of a constant ratio approximation algorithm for the $U^\varGamma$ model. Our main result is to answer positively to this question by providing a 4.5 approximation for $U^\varGamma$ model based on dynamic programming.

This research has benefited from the support of the ANR project ROBUST [ANR-16-CE40-0018].

1 Introduction

Bin packing is the problem of assigning a given set of n items, each item of a specified size, to the smallest number of unit capacity bins. The problem has been the subject of study in an extensive body of research initiated by several publications in the 1970s including the work of Johnson et al. [11]. The problem is $\mathcal {NP}$-hard and in fact a straightforward reduction from the partition decision problem implies that it is $\mathcal {NP}$-hard to determine whether a bin-packing instance has a solution using only two bins. This also shows that the problem cannot be approximated within a factor less than 3/2. An approximation factor guarantee of 3/2 has been proven for the first-fit decreasing algorithm by Simchi-Levi [16]. Much of the research has concentrated on the asymptotic setting where n tends to infinity, and in the online setting where the instance is not given in advance but each item is revealed and packed one at a time. A fully polynomial-time approximation scheme for the offline asymptotic problem is due to Karmarkar and Karp [12]. The best asymptotic and absolute online competitive ratios of 1.578 and 5/3, respectively, are due to Balogh et al. in [4] and [3], respectively.

In many applications, the sizes of the items to be packed are not fully known at the time that the packing is carried out. In cargo shipping, for example, the actual weight of a container may deviate from its declared weight or its measurements may be inaccurate. Bin packing has also been used to model the assignment of elective surgeries to operating room in hospitals [8]. Here a bin is a shift of a properly equipped and staffed operating room for performing a certain type of elective surgeries. The room scheduler has to fit in the bins as many cases (patients) as possible. In this setting clearly the length of time of performing each surgery is subject to uncertainty for example in the event of complications. One way to model the uncertainty that falls into the framework of robust optimization is to assume that the sizes are uncertain parameters taking any value in a given set $U\subset \mathbb {R}^n$, where each $a \in U$ represents a possible scenario. This leads to the following problem (where the description of U is sometimes not explicit to avoid exponential length in n)

Classically, robust combinatorial optimization has dealt with uncertain objective, meaning that the cost vector c can take any value in set U, unlike RBP where the uncertainty affects the feasibility of the solutions. In that context, it is well-known that arbitrary uncertainty sets U lead to robust counterparts that are hardly approximable. For instance, the robust knapsack is not approximable at all [1], while the shortest path, the spanning tree, the minimum cut, and the assignment problem do not admit constant-ratios approximation algorithms, e.g. [13, 14]. Furthermore, describing U by an explicit list of scenarios runs the risk of over-fitting so the optimal solutions may become infeasible for small variations outside U. These two drawbacks are usually tackled by using more specific uncertainty sets, defined by simple budget constraints. One of these widely used uncertainty sets, $U^\varGamma$, supposes that the size of each item is either its given nominal size $\bar{a}_i$, or its peak value $\bar{a}_i+ \hat{a}_i$. Furthermore, in any scenario, at most $\varGamma \in \mathbb {N}$ of the items may assume their peak value simultaneously. Formally, $U^\varGamma$ can be defined as $U^\varGamma =\{a | \forall i \in [n], a_i \in \{\bar{a}_i, \bar{a}_i + \hat{a}_i\} \text{ and } \sum _{i\in [n]}(a_i -\bar{a}_i)/\hat{a}_i \le \varGamma \}$.¹ Set $U^\varGamma$ has been widely used in robust combinatorial optimization with a constant number of constraints because the set essentially preserves the complexity and approximability properties of the nominal problem. The result was initially proposed for min-max problems in [6], and was independently extended to uncertain constraints in [2, 9], contrasting with the aformentionned uncertain objective. We also consider a second uncertainty set (used in [10, 18], among others), characterized again by $\bar{a}$ and $\hat{a}$, as well as the number $\varOmega \in [0,1]$ stating how much deviation can be spread among all sizes, formally $U^\varOmega =\{a\in \times _{i\in [n]} [\bar{a}_i, \bar{a}_i + \hat{a}_i]\mid \sum _{i\in [n]}(a_i -\bar{a}_i) \le \varOmega \}.$ From the approximability viewpoint, set $U^\varOmega$ benefits from similar positive results as $U^\varGamma$, see [15].

The above positive complexity results (e.g. [9, 15]) imply, for instance, that there exists a fully-polynomial time approximation scheme (FPTAS) for the robust knapsack problem with uncertain profits and uncertain weights belonging to $U^\varOmega$ and/or $U^\varGamma$. Interestingly, these positive results do not extend to most scheduling problems (because they involve non-linearities) and to the bin-packing problem (because it involves a non-constant numbers of robust constraints). While in a previous paper [7] (with authors in common) we provided approximability results on robust scheduling, no such results have yet been proposed for the bin-packing problem, the only previous work focusing on numerical algorithms [17]. The purpose of this paper is to fill these gaps, as we present constant-ratio approximation algorithms the bin-packing problem, both for $U^\varOmega$ and $U^\varGamma$.

Notations, Problems Definitions, and Next-Fit Algorithm. In this paper we consider two special cases of RBP. In the first one, $\varGamma \textsc {RBP}$, the input is $\mathcal {I}=(n,\overline{a},\hat{a},\varGamma )$ where $n\in \mathbb {N}$, and we assume that $U=U^\varGamma$. In the second one, $\varOmega \textsc {RBP}$, the input is $\mathcal {I}=(n,\overline{a},\hat{a},\varOmega )$ where $n\in \mathbb {N}$, $\overline{a}\in [0,1]^n$, $\hat{a}\in [0,1]^n$, and $\varOmega \in [0,1]$, and we assume that $U=U^\varOmega$.

Let us now provide some important notations that will allow us to restate $\varGamma \textsc {RBP}$ and $\varOmega \textsc {RBP}$ in a more convenient way. Given $n \in \mathbb {N}$, sets $\{0,1,\ldots ,n\}$ and $\{1,\ldots ,n\}$ are respectively denoted $[n]_0$ and [n]. Set $\{i,\ldots ,j\}$ is denoted by $\llbracket i,j\rrbracket$. Given a vector $v\in [0,1]^n$ and a subset $X \subseteq [n]$, we define $v(X)=\sum _{i \in X}v_i$. Given two vectors $\overline{a}\in [0,1]^n$, $\hat{a}\in [0,1]^n$ and a subset of items $X \subseteq [n]$, we define $\hat{a}_\varOmega (X) =\min \{\hat{a}(X),\varOmega \}$, $\varGamma (X)$ as the set of $\varGamma$ items in X with largest $\hat{a}$ values (ties broken by taking smallest indices), or $\varGamma (X)=X$ if $|X| < \varGamma$, and $\hat{a}_{\varGamma }(X) = \hat{a}(\varGamma (X))$. Accordingly, we define the fill of a bin $b\subseteq [n]$ as $f_\varGamma (b)=\overline{a}(b)+\hat{a}_{\varGamma }(b)$ for set $U^\varGamma$, and $f_\varOmega (b) = \bar{a}(b) + \hat{a}_\varOmega (b)$ for set $U^\varOmega$. The fill of a bin for a general uncertainty set U is denoted as $f_U(b) = \max _{a\in U}a(b)$.

Consider the following example. We are given an ordered set of pairs $(\bar{a}_i,\hat{a}_i)$, $X=\{(0.3,0.2),(0.4,0.2),(0.3,0.1),(0.2,0.5)\}$ with $\varGamma = 2$ and $\varOmega = 0.3$. Thus, $\varGamma (X) = \{(0.3,0.2),(0.2,0.5)\}$, $\bar{a}(X) = 1.2$, $\hat{a}_\varGamma (X) = 0.7$, and $f_\varGamma (X) = 1.9$. Similarly, $\hat{a}_\varOmega (X) = 0.3$ and $f_\varOmega (X) = 1.0$.

Now, observe that $\max _{a\in U}\sum _{i\in b_j }a_i \le 1$ (the constraint required in RBP) is equivalent to $f_U(b) \le 1$, and thus to $f_\varGamma (b_j) \le 1$ for $\varGamma \textsc {RBP}$ and $f_\varOmega (b_j) \le 1$ for $\varOmega \textsc {RBP}$. For example in $\varGamma \textsc {RBP}$, $f_\varGamma (b_j) \le 1$ simply means that the total nominal ($\overline{a}$) size of the items plus the deviating size ($\hat{a}$) of the $\varGamma$ largest (in $\hat{a}$ values) items must not exceed one. Thus, the two optimization problems studied in this paper can be equivalently formulated in the following way.

    

The optimal solution value or cost of either problem is denoted by $\textsf {OPT} (\mathcal {I})=k^*$ ($\mathcal {I}$ may be omitted when the instance is clear from the context) and a corresponding optimal solution is denoted by $s^*=\{b_1^*,b_2^*,\ldots ,b^*_{k^*}\}$. We introduce in Algorithm 1 a variant of the standard next fit algorithm.

Structure of the Paper. In Sects. 2 and 3, we analyze the ratio provided by Next-Fit for $\varOmega \textsc {RBP}$ and $\varGamma \textsc {RBP}$, respectively. For $\varOmega \textsc {RBP}$, using ordering (1) (non-increasing ordering on $\frac{\hat{a}_i}{\bar{a}_i}$) the ratio is equal to 2. For $\varGamma \textsc {RBP}$, using ordering (2) (non-increasing ordering on $\hat{a}_i$), the ratio is bounded by $2(\varGamma +1)$ (and can be improved to 2 for $\varGamma =1$). As Theorem 4 shows that neither ordering (1) or (2) leads to a constant ratio using Next-Fit, this raises the question the existence of a constant approximation for $\varGamma \textsc {RBP}$. In Sect. 4 we first review some basic ideas and explain why they are not sufficient. Then, we introduce the key elements necessary to develop our dynamic programming algorithm (DP) in Sect. 5. The latter gives a ratio of 4.5 for $\varGamma \textsc {RBP}$ and any $\varGamma \in \mathbb {N}$, which is our main result. The complete proofs of Theorems and Lemmas with a $\varvec{(\star )}$ symbol can be found in the full version of this paper [5].

2 Next-Fit for $\varOmega \textsc {RBP}$

Unlike the classical bin-packing problem, executing Next-Fit on arbitrarily ordered items can lead to arbitrarily bad solutions. For example, given $\epsilon$ with $0<\epsilon \le \frac{1}{2n}$, consider an instance with $\varOmega =1-\epsilon$, and items $((2\epsilon ,0),(0,1-\epsilon ),\ldots , (2\epsilon ,0),(0,1-\epsilon ))$, where item $i\in [n]$ is denoted by the pair $(\bar{a}_i,\hat{a}_i)$. Using this ordering, Next-Fit will create n / 2 bins $b_j$ with $f_{\varOmega }(b_j) > 1$ for any $j \in [n]$ (which will be turned into n bins $\{b^1_j,b^2_j\}$), whereas the optimal solution uses 2 bins. This example also illustrates that, unlike in the standard bin-packing, the total size argument no longer apply to the robust counterpart as having $f_{\varOmega }(b_j) > 1$ for any $j \in [n]$ does not imply a large (depending on n) lower bound on the optimal.

Next, we consider an ordering of the items such that

$$\begin{aligned} \hat{a}_1/\bar{a}_1 \ge \cdots \ge \hat{a}_n/\bar{a}_n. \end{aligned}$$

(1)

Lemma 1

Suppose that the items are ordered according to (1). Then $k'\le k^*$.

Proof

Consider an optimal solution $b^*_1,\ldots ,b^*_{k^*}$ and the subset of optimal bins given by $G^* = \{j \in [k^*] \mid \hat{a}(b^*_j) >\varOmega \}$. Let

$$\begin{aligned} A = \sum _{i\in [n]}\left( \bar{a}_i+\hat{a}_i\right) = \sum _{j=1}^{k'}\left( \bar{a}(b_j) + \hat{a}(b_j) \right) = \sum _{j=1}^{k^*}\left( \bar{a}(b^*_j)+\hat{a}(b^*_j)\right) . \end{aligned}$$

Let G denote the first $|G^*|$ bins opened in Step 1 of Next-Fit. If $k'\in G$ then clearly $k'\le k^*$. Otherwise, it can be observed that for each $l\in G$, $\bar{a}(b_l) > 1-\varOmega$ (as $\bar{a}(b_\ell ) + \hat{a}_\varOmega (b_\ell ) > 1$ and $\hat{a}_\varOmega (b_\ell ) \le \varOmega$) and $1-\varOmega \ge \max _{j\in G^*}\bar{a}(b^*_j)$ (as $f_\varOmega (b_j) \le 1)$. Thus, $\sum _{j\in G}\bar{a}(b_j) > \sum _{j\in G^*}\bar{a}(b^*_j)$ and so by the assumed ordering (1) of the items, following a standard knapsack argument, $\sum _{j\in G}\hat{a}(b_j) > \sum _{j\in G^*}\hat{a}(b^*_j)$. Letting $\bar{G} = [k']\setminus G$ and $\bar{ G}^*=[k^*]\setminus G^*$, it follows that

(equality may hold throughout if $G^*=\emptyset$). Further, for each $j\in \bar{G}\setminus \{k'\}$, $\bar{a}(b_j) +\hat{a}(b_j) \ge f(b_j) > 1$ and for each $j\in \bar{G}^*$, $\bar{a}(b^*_{j}) +\hat{a}(b^*_{j})\le 1$. Therefore, $|\bar{G}|\le \left\lceil \sum _{j\in \bar{G}}\left( \bar{a}(b_j) + \hat{a}(b_j)\right) \right\rceil \le \left\lceil \sum _{j\in \bar{G}^*}\left( \bar{a}(b^*_j)+\hat{a}(b^*_j) \right) \right\rceil \le |\bar{G}^*|$ and $k'\le k^*$ as claimed.    $\square$

The lemma combined with Step 2 of Next-Fit immediately imply the following theorem.

Theorem 1

If the items are ordered according to (1) then Next-Fit is a 2-approximation algorithm for $\varOmega \textsc {RBP}$.

3 Next-Fit for $\varGamma \textsc {RBP}$

From now on, we focus on problem $\varGamma \textsc {RBP}$. Remark first that using an arbitrary ordering leads to arbitrarily bad solutions, considering $\varGamma =1$ and the same items $((2\epsilon ,0),(0,1-\epsilon ),\ldots , (2\epsilon ,0),(0,1-\epsilon ))$ as in the previous section. Thus, we consider here an ordering of the items such that

$$\begin{aligned} \hat{a}_1 \ge \cdots \ge \hat{a}_n. \end{aligned}$$

(2)

The main result of this Section is the following.

Theorem 2

$\varvec{(\star ).}$ If the items are ordered according to (2) then Next-Fit is a $2(\varGamma +1)$-approximation algorithm for $\varGamma \textsc {RBP}$.

The proof of Theorem 2 can be found in the full version of this paper [5].

We show here a simplified analysis showing that for $\varGamma =1$, Next-Fit with ordering (2) is a 2-approximation.

The deviating item of bin j in a fixed optimal solution $s^*$ and in the solution of Next-Fit are denoted by singleton sets $\{i^*_j\} = \varGamma (b^*_j)$ and $\{i_j\} = \varGamma (b_j)$, respectively. We order the bins of $s^*$ such that $i^*_j \ge i^*_{j+1}$. Notice that by definition of Next-Fit and ordering (2) we also have $i_j \ge i_{j+1}$.

Lemma 2

Suppose that the items are ordered according to (2) and that $\varGamma =1$. Then $k'\le k^*$.

Proof

Suppose by contradiction that $k'>k^*$. Let $b_1,\ldots ,b_{k'}$ be the bins opened at Step 1 of Next-Fit and notice that $f_\varGamma (b_j)=\overline{a}(b_j)+\hat{a}_\varGamma (b_j)>1$ for each $j\in [k'-1]$, while $\overline{a}(b^*_j)+\hat{a}_\varGamma (b^*_j)\le 1$ for each $j\in [k^*]$. We prove next by induction on $\ell \in [k^*]$ that

$$\begin{aligned} \sum _{j=1}^{\ell } \overline{a}(b_j) > \sum _{j=1}^{\ell } \overline{a}(b^*_j). \end{aligned}$$

(3)

For $\ell =1$, we have $i_1=i^*_1=1$ and (3) follows immediately from $\hat{a}_\varGamma (b_1)=\hat{a}_\varGamma (b_1^*)$. Suppose now that induction hypothesis is true for $\ell -1$. By definition of $i^*_\ell$ and $i_\ell$, we know that $[i^*_\ell -1] \subseteq \bigcup _{j=1}^{\ell -1}b^*_j$ and $[i_\ell -1] = \bigcup _{j=1}^{\ell -1}b_j$. Using induction hypothesis, we get that $i_\ell \ge i^*_\ell$, and accordingly $\hat{a}_\varGamma (b_\ell ) \le \hat{a}_\varGamma (b_\ell ^*)$. As $l \le k^* < l$, we have $f_{\varGamma }(b_l) > 1$, leading to $\overline{a}(b_\ell ) > \overline{a}(b_\ell ^*)$.

Thus, for $l=k^*$ we get $\sum _{j=1}^{k^*} \overline{a}(b_j) > \sum _{j=1}^{k^*} \overline{a}(b^*_j)= \sum _{i\in [n]}\overline{a}_i$, which is impossible.    $\square$

As in the previous section, we obtain the following theorem.

Theorem 3

If the items are ordered according to (2) and $\varGamma =1$ then Next-Fit is a 2-approximation algorithm for $\varGamma \textsc {RBP}$.

To complete the analysis, we establish the following lower bound on the ratio of Next-Fit.

Theorem 4

$\varvec{(\star ).}$ If the items are ordered according to (2) or (1), then the approximation ratio of Next-Fit for $\varGamma \textsc {RBP}$ is at least $\frac{2\varGamma }{3}$.

Proof

Let us define an instance where the ordering (2) can lead to Step 1 of Next-Fit using $k'=\varGamma$ bins while $\textsf {OPT} =3$. Every row of the $\varGamma \times \varGamma$ matrix below corresponds to the set of items in a bin (after the Step 1) of Next-Fit algorithm

$$\begin{aligned} \begin{array}{l l l l } (\epsilon ,1/\varGamma -\delta _1) &{} (0,1/\varGamma -\delta _1) &{} \dots &{} (0,1/\varGamma -\delta _1) \\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ (\epsilon ,1/\varGamma -\delta _{\varGamma }) &{} (0,1/\varGamma -\delta _{\varGamma }) &{} \dots &{} (0,1/\varGamma -\delta _{\varGamma }) \end{array} \end{aligned}$$

(4)

where $\epsilon \le 1/\varGamma$ and $\delta _1 \le \dots \le \delta _{\varGamma } < \epsilon /\varGamma$. On the one hand, $\epsilon + \varGamma \cdot (1/\varGamma - \delta _{l}) >1$ for each $l\in [\varGamma ]$, so step 1 of Next-Fit outputs $\varGamma$ bins. On the other hand, an optimal solution can pack all the items above except the ones in the first column into a single bin because $\varGamma \cdot 1/\varGamma -\delta _1 \le 1$. Further, the total weight of the first $\varGamma /2$ items of the first column sums up to $\varGamma /2 \cdot (1/\varGamma + \epsilon ) - \sum _{l=1}^{\varGamma /2} \delta _l \le 1 - \sum _{l=1}^{\varGamma /2} \delta _l \le 1,$ and similarly for the last $\varGamma /2$ items, so an optimal solution may pack the first column using two bins. Finally, instance (4) shows that Next-Fit produces a solution $2\varGamma /3$ times worse than the optimal one.

This instance can be adapted to establish a lower bound for the approximation ratio of Next-Fit when items are ordered according to (1); see [5].    $\square$

4 First Ideas to Get a Constant Ratio for $\varGamma \textsc {RBP}$

We maintain the assumption that the items are ordered according to (2).

4.1 Attempts to Get a Constant Ratio

We discuss below some natural arguments to get constant ratios.

Attempt 1: Using a Classical Size Argument. Next-Fit without a particular ordering applied to instance of Sect. 3 leads to a solution with $k'=n/2$ bins (at the end of Step 1) where $f_\varGamma (b_j) > 1$ for each bin, while $\textsf {OPT} = 2$. This example shows that even if all bins are “full” (relatively to $f_\varGamma$), it does not provide a lower bound on the optimal number of bins. Moreover, as shown in Theorem 4, none of the two orders considered in the previous section leads to a constant ratio using Next-Fit.

Attempt 2: Using the Duality with Makespan Minimization. Given input $\mathcal {I}$, we could guess $k^*=\textsf {OPT} (\mathcal {I})$, and then consider the input $(\mathcal {I},k^*)$ as an input of robust makespan minimzation (which was studied in [7]). Using any $\rho$-approximation for the later problem (for example $\rho =3$ in [7]), we could get in polynomial time a solution with $k^*$ bins an such that $f_\varGamma (b_j) \le \rho$. The last step would be to convert this solution into a solution of $\varGamma \textsc {RBP}$ by unpacking each bin (with $f_\varGamma (b_j) \le 3$) into several bins $b_j^l$ with $f_\varGamma (b_j^l) \le 1$. However, even if $\rho$ were arbitrarily close to 1, it is not possible to bound (for a fixed j) the number of bins $b_j^l$ by a constant as showed in the instance containing n items $(\frac{\epsilon }{n},1-\frac{\epsilon }{n})$ and $\varGamma =1$. While all items fit into a single bin with capacity lower than $1+\epsilon$, they require n bins of capacity 1 to be packed.

Attempt 3: Guessing the Profile of an Optimal Solution. Let $\mathcal {I}$ be a input of $\varGamma \textsc {RBP}$. Given a solution $s=\{b_j, j \in [k]\}$ for this input, we define $P(s)=\{\varGamma (b_j), j \in [k]\}$ as the profile of s and $\tilde{P}_j(s)=\{i \mid i\in \varGamma (b_\ell ) \text{ for } \text{ some } \ell \in [j]\}$ as all deviating items in the first j bins. Let $s^*=\{b^*_j, j \in [k^*]\}$ be an optimal solution. To get some insight on the problem, let us assume that we know $P(s^*)$ (even if this cannot be guessed in polynomial time). We show how we can use $P(s^*)$ to get a 2-approximation algorithm. Without loss of generality, we can always assume that $|\varGamma (b^*_j)| = \varGamma$ for any j, as otherwise we can add $\varGamma -|\varGamma (b^*_j)|$ dummy items of size (0, 0) to $b^*_j$. Remember that the items are sorted in non-increasing order of their deviating values ($\hat{a}_i \ge \hat{a}_{i+1}$). For any $j \in [k^*]$, let $i_j^* = \max (\varGamma (b^*_j))$ be the smallest (in term of $\hat{a}$ value) deviating item of bin j (when $\varGamma =1$, $\{i_j^*\} = \varGamma (b^*_j)$ as in the previous section). Without loss of generality, let us assume that bins are sorted such that $i_j^* \ge i_{j+1}^*$. Now, given $P(s^*)$, in the first phase we construct a solution s by packing items of $P(s^*)$ as they were packed in $s^*$, meaning that we define $b_j = \varGamma (b^*_j)$ for $j \in [k^*]$. Let $X = [n] \setminus \bigcup _{j \in [k^*]}\varGamma (b^*_j)$ be the set of remaining items. We now pack X in the following second phase, starting with $j=1$. Notice that in the description of the algorithm below, we consider that for $j \in [k^*]$, $b_j$ already contains $\varGamma (b^*_j)$, whereas for any $j > k^*$, $b_j$ is initially empty.

Step 1 :

pack items of X (by decreasing $\hat{a}$ values) in $b_j$ until $f_\varGamma (b_j)>1$ or $X = \emptyset$

Step 2 :

if $X \ne \emptyset$, $j=j+1$, and go to step 1.

Let j be the bin such that X is empty after filling $b_j$. Let $k'$ be the number of bins used by this algorithm. Notice that if $j \le k^*$ then $k'=k^*$ (because of the pre-packing of item of $P(s^*)$), and otherwise $k' = j$.

Lemma 3

$k' \le k^*$, implying a 2-approximation as we can convert the solution of Next-Fit into a feasible solution of $2k'$ bins by repacking the last added item in each bin in a separate bin.

Proof

Assume by contradiction that $k' > k^*$. Informally, as an item $i\in [n]\setminus \tilde{P}_{k^*}(s^*)$ does not deviate in $s^*$, we need to ensure that this is also the case in s. Let us prove by induction on j that the items packed greedily in Step 1 satisfy

$$\begin{aligned} \hat{a}_{i} \le \hat{a}_{i^*_j}, \forall i\in b_j\setminus \tilde{P}_{k^*}(s^*), j\in [k^*]. \end{aligned}$$

(5)

Let $j=1$, and suppose there is $i\in b_1\setminus \tilde{P}_{k^*}(s^*)$ such that $\hat{a}_{i} > \hat{a}_{i^*_1}$. Then, because $\hat{a}_{i^*_1}\ge \hat{a}_{i^*_j}$ for $j>1$, $\hat{a}_{i} > \hat{a}_{i^*_j}$ for each j so $i\in \tilde{P}_{k^*}(s^*)$, a contradiction. Now, consider bin $b_{j+1}$. By induction, we have that $\sum _{\ell \in [j]}\overline{a}(b_\ell )+\hat{a}(\tilde{P}_j(s))>j \ge \sum _{\ell \in [j]}\overline{a}(b_\ell ^*)+\hat{a}(\tilde{P}_j(s^*))$, so $\tilde{P}_j(s)=\tilde{P}_j(s^*)$ implies

$$\begin{aligned} \sum _{\ell \in [j]}\overline{a}(b_\ell ) > \sum _{\ell \in [j]}\overline{a}(b_\ell ^*). \end{aligned}$$

(6)

Let $X_j$ be the set of items of X left after packing bin $b_j$ by the above procedure and $X_j^*$ be the the set of items of X left after the optimal solution packs bin $b_j^*$. Inequality (6) and the ordering used in Step 1 imply that $\lambda \ge \lambda ^*$, where $\lambda =\min (X_j)$ and $\lambda ^* = \min (X_j^*)$. Therefore, if there exists $i \in b_{j+1} \setminus \tilde{P}_{k^*}(s^*)$ such that $\hat{a}_i > \hat{a}_{i^*_{j+1}}$, then $\hat{a}_{\lambda ^*} \ge \hat{a}_{\lambda } \ge \hat{a}_i > \hat{a}_{i^*_{j+1}}$, and thus $\hat{a}_{\lambda ^*} > \hat{a}_{i^*_\ell }$ for any $l \in \llbracket j+1,k^*\rrbracket$, which is a contradiction as item $\lambda ^*$ is in X and thus does not deviate in the considered optimal.

Now that Property (5) is proved, let us get our contradiction from $k' > k^*$. Indeed, if $k'>k^*$ then $\sum _{i\in [n]}\overline{a}_i > k^* - \hat{a}(\tilde{P}_{k^*}(s^*)) \ge \sum _{j \in [k^*]}\overline{a}(b_j^*)$ where the first inequality follows from $f_\varGamma (b_j)>1$ for $j\in [k^*]$ and Property (5), and the second one follows from $\sum _{j \in [k^*]}\overline{a}(b_j^*)+\hat{a}(\tilde{P}_{k^*}(s^*))\le k^*$. This implies a contradiction.    $\square$

Even if the above procedure relies on a guessing step which is not polynomial, its core idea has similarities with both the analysis of Next-Fit in the proof of Theorem 2 (see [5]) and with the DP algorithm detailed later in this paper, where we only guess the deviating item with the smallest deviation of each bin (one at a time), and we pack $\varGamma -1$ items “better” than the one packed in $P(s^*)$, at the expense of a few extra bins.

4.2 Restricting Our Attention to Small Items

We define $\varGamma \textsc {RBP}$ with small values as the $\varGamma \textsc {RBP}$ problem restricted to inputs where for any $i \in [n]$, $\hat{a}_i \le \frac{1}{\varGamma }$ and $\hat{a}_i \le \frac{1}{\varGamma }$. Below we give a justification for restricting our attention to $\varGamma \textsc {RBP}$ with small values.

Lemma 4

Any polynomial $\rho$-approximation for $\varGamma \textsc {RBP}$ with small values implies a polynomial $(\rho +\rho _{bp})$-approximation for $\varGamma \textsc {RBP}$, where $\rho _{bp}$ is the best known ratio of a polynomial time approximation for classical bin-packing.²

Proof

Given an instance $\mathcal {I}$ of $\varGamma \textsc {RBP}$, we define the small items $\mathcal {S}=\{i\in [n]: \overline{a}_i\le 1/\varGamma \text{ and } \hat{a}_i\le 1/\varGamma \}$ and the large item as $\mathcal {B}=[n]\setminus \mathcal {S}$. We use our $\rho$-approximation algorithm to pack $\mathcal {S}$ into $k_\mathcal {S}$ bins, implying $k_\mathcal {S}\le \rho \textsf {OPT} (\mathcal {S}) \le \rho \textsf {OPT} (\mathcal {I})$. Then, we observe that in any packing of $\mathcal {B}$, each bin contains no more than $\varGamma$ items, so that all items deviate in these bins. Hence, $\varGamma \textsc {RBP}$ for instance $(\mathcal {B},\varGamma )$ is equivalent to the classical bin-packing problem for items $\mathcal {B}'$ where the weight of each item $i\in \mathcal {B}'$ is given by $\overline{a}_i+\hat{a}_i$. This implies that $\textsf {OPT} _{bp}(\mathcal {B}')=\textsf {OPT} (\mathcal {B})$ (where $\textsf {OPT} _{bp}$ denotes the optimal value in classical bin-packing), and that any solution for $\mathcal {B}'$ is a solution of $\mathcal {B}$. Thus, we use a $\rho _{bp}$-approximation algorithm for classical bin-packing to pack $\mathcal {B}'$ in $k_{\mathcal {B}}$ bins, and use the same packing for items in $\mathcal {B}$. Note that $k_{\mathcal {B}} \le \rho _{bp} \textsf {OPT} _{bp}(\mathcal {B}) = \rho _{bp} \textsf {OPT} (\mathcal {B}) \le \rho _{bp} \textsf {OPT} (\mathcal {I})$. We obtain a packing of $\mathcal {I}$ with cost $k_\mathcal {S}+k_\mathcal {B}\le (\rho + \rho _{bp}) \textsf {OPT} (\mathcal {I})$.    $\square$

Observation 1

Given an instance $\mathcal {I}$ to the $\varGamma \textsc {RBP}$ with small values, any subset $X\subseteq [n]$ can be packed in $\lceil \frac{|X|}{\varGamma /2} \rceil$ bins.

Notice that instances with small items are not easier to approximate by Next-Fit because instance (4) from Sect. 3 uses small items.

4.3 Guessing of the Full Profile and Considering Only Small Items

Let us now explain why mixing the two previous ideas is promising. As in attempt 3 where we know the full profile, we want to construct for any j bins $\{b_1,\dots ,b_j\}$ such that their total $\overline{a}$ is larger than the total value of $\overline{a}$ packed by the first j bins of $s^*$ (the considered optimal solution), as in inequality (6). Instead of guessing the full profile $P(s^*)$, we want to design a DP algorithm (that guesses $i_{j^*}$ one at the time) with the following intuitive outline. Start with $j=1$.

• guess item $i_j^*$, the smallest (in $\hat{a}$ value) deviating item of $b_j^*$, and pack it in $b_j$

• then, as the $\varGamma -1$ other deviating items in $b_j^*$ are unknown and we want to pack more of the nominal size $\overline{a}$, packs separately $\varGamma -1$ items with larger $\overline{a}$ values (among items with $\hat{a}$ values greater than $\hat{a}_{i_j^*}$). Consider that these $\varGamma -1$ items are put in the “trash” (at the very end we will pack all items of the trash in a few additional bins)

• keep filling bin $b_j$ greedily (by non-increasing $\hat{a}$ values) until exceeding 1

• make a recursive call with $j+1$

If $s^*$ uses $k^*$ bins, we wish to output a solution s with $k^*$ bins exceeding one, and $(\varGamma -1)k^*$ items in the trash. This almost feasible solution can be converted into a regular one with $3k^*$ bins by removing one item from each bin and adding them to the trash, and packing the $\varGamma k^*$ items of the trash into $2k^*$ bins, which is possible according to Observation 1. This sketches the core ideas of the DP. However, the actual DP presented below needs to be more involved for the following reasons. Consider $j=1$ for convenience and let $B = \llbracket 1,i_1^*-1\rrbracket$.

First, notice that items of B could be packed (as deviating items) in a bin other than $b^*_1$ in $s^*$, and we may have $|B| > \varGamma -1$. Thus, instead of trashing only $\varGamma -1$ items of B, we have to trash all of them, and count the number of trashed items to ensure that at the end at most $(\varGamma -1)k^*$ items are trashed. To summarize, the trash will represent the union of the $(\varGamma -1)$ larger (in $\hat{a}$ values) deviating items of each bin. Moreover, we want to maintain that the accumulated nominal ($\overline{a}$) size of trashed items in s is larger than the accumulated nominal size of deviating items in $s^*$.

Second, notice that in $s^*$, items of $\llbracket i^*_1+1,i^*_2-1 \rrbracket$ are either in $b^*_1$ as non-deviating items or in a $b^*_j$, $j \ge 2$ as deviating items (meaning that they are trashed items in s). Thus, if we incorrectly pack some of these items in $b_1$ instead of trashing them, these items will not be available when considering $b_2$, and we may not be able to ensure then that trashed items in s have a larger $\overline{a}$ value than the deviating items in $s^*$.

In the next section we describe the full version of the DP. To that end, we first need to introduce formally the notion of trash.

5 Approximating $\varGamma \textsc {RBP}$ with Small Values

Bin-Packing with Trash. For any $X\subseteq [n]$, we define $\tilde{a}_{\varGamma }(X) = \varGamma \hat{a}_1(X)$ ($\tilde{a}_{\varGamma }(X)$ is $\varGamma$ times the largest deviating value of an item in X) and $\tilde{f}(X) = \overline{a}(X)+\tilde{a}_{\varGamma }(X)$. We introduce next a decision problem $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ related to $\varGamma \textsc {RBP}$.

Notice that although each item is small in $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, it is possible to have an item i such that $\tilde{f}(\{i\}) > 1$, implying that i must be put in the trash. We show below how deciding $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ is enough to approximate $\varGamma \textsc {RBP}$.

Lemma 5

For any input $\mathcal {I}$ of $\varGamma \textsc {RBP}$ and $k^* = \textsf {OPT} (\mathcal {I})$, $(\mathcal {I},k^*,(\varGamma -1)k^*)$ is a yes input of $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$.

Proof

Given an optimal solution of size $k^*$ of $\varGamma \textsc {RBP}$ problem we create a solution to $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ problem as follows. Let $b^*_j$ be a bin of the considered optimum. Let $N_j$ be the non-deviating items of $b^*_j$, i.e., $b^*_j = N_j \cup \varGamma (b^*_j)$. Let $X= \max (\varGamma (b^*_j))$ (the smallest deviating item of $b^*_j$) if $|\varGamma (b^*_j)|=\varGamma$ and $X = \emptyset$ otherwise. We define $b'_j = N_j \cup X$, and add items of $Y=b^*_j \setminus b'_j$ into the trash. Notice Y is either the set of $\varGamma -1$ largest deviating object of $b^*_j$, or is equal to $\varGamma (b^*_j)$ when $|\varGamma (b^*_j)| < \varGamma$. This is a feasible solution for $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ problem as $\tilde{f}(b'_j) = \overline{a}(b'_j)+\tilde{a}_{\varGamma }(b'_j)$, where $\overline{a}(b'_j) \le \overline{a}(b^*_j)$ and $\tilde{a}_{\varGamma }(b'_j)=\tilde{a}_{\varGamma }(X)\le \hat{a}_{\varGamma }(b^*_j)$, and as there are at most $(\varGamma -1)k^*$ items in the trash.    $\square$

Lemma 6

For any input $\mathcal {I}$ of $\varGamma \textsc {RBP}$ and integer k, given a solution of $(\mathcal {I},k,\varGamma k)$ of $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, we can compute in polynomial time a solution of 3k bins for $\mathcal {I}$.

Proof

Given a solution $b_1,\ldots ,b_k$, T for $(\mathcal {I},k,\varGamma k)$ of $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ the bins remain feasible in $\varGamma \textsc {RBP}$ as $f_\varGamma (b_j)=\overline{a}(b_j)+\hat{a}_{\varGamma }(b_j) \le \overline{a}(b_j)+\tilde{a}(b_j)=\tilde{f}(b_j)$. Then, Observation 1 implies that the trash T can be packed into $\lceil k\varGamma /(\varGamma /2) \rceil \le 2k$ additional bins.    $\square$

A DP Algorithm for $\varvec{\varGamma }$RBP-T. The objective of this section is to define a DP algorithm that will be used to decide the $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ problem. To this aim, we define $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ (generalized robust bin-packing with trash), an optimization problem that the DP algorithm will solve in a relaxed way. To define $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, we consider a fixed instance $\mathcal {I}$ of $\varGamma \textsc {RBP}$ with items ordered according to (2) and an integer k.

The objective of $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ is to pack a part (defined by $\llbracket q,k\rrbracket$) of an $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ instance given a fixed budget of resources (the number of bins and the size of the trash) while minimizing the total nominal size of items in the dummy bin $b_0$. The last constraint (the deviating item of $b_\ell$ is q) may appear artificial at first sight, but comes from the fact that the DP will guess at each new bin the largest items that should be packed in it, and therefore this constraint ensures that every optimal solution must pack q in $b_\ell$ as well.

Definition 1

(almost feasible solution). We say that a bin b exceeds by at most one item iff $\tilde{f}(b)> 1$ and $\tilde{f}(b \setminus \{i\})\le 1$ where $i=\max (b)$. Given an input $(q,t,\ell )$ of $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, we say that a solution is almost feasible iff all the above constraints of $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ are respected, except that for any $j \in \llbracket \ell ,k \rrbracket$, we allow that $b_j$ exceeds by at most one item instead of $\tilde{f}(b_j) \le 1$.

The relation between $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ and $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ is characterized in the two following lemmas whose proofs can be found in [5].

Lemma 7

$\varvec{(\star ).}$ For any $\mathcal {I}$ input of $\varGamma \textsc {RBP}$ and k such that $(\mathcal {I},k,(\varGamma -1)k)$ is a yes input of $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, there exists $q$ and $t$ such that $\textsf {OPT} (q,t,1) = 0$.

Lemma 8

$\varvec{(\star ).}$ Let us fix $\mathcal {I}$ an input of $\varGamma \textsc {RBP}$ and k an integer. For any $q\in [(\varGamma -1)k], t = (\varGamma -1)k-(q-1)$, given an almost feasible solution of $\mathcal {I}'=(q,t,1)$ of cost 0 for $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, we can compute in polynomial time a solution of $(\mathcal {I},k,\varGamma k)$ of $\varGamma \textsc {RBP}\hbox {-}\textsc {T}$.

Thus, Lemmas 6 and 8 show that providing an almost feasible solution for $(q,t,1)$ of cost 0 for $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$ implies a solution of size 3k for $\varGamma \textsc {RBP}$.

Let us now define a DP algorithm $DP(\mathcal {I})$ ($\mathcal {I}$ is an input of $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$) that provides an almost feasible solution s with $c(s) \le \textsf {OPT} (\mathcal {I})$ (where $\textsf {OPT} (\mathcal {I})$ is by definition the optimal cost of a feasible solution). We provide below a gentle description of the DP. Given an instance $\mathcal {I}=(q,t,\ell )$, the DP starts by guessing $(q^*,t^*)$, where

• $q^*=\min (b^*_{l'})$ for a bin $b^*_{l'}$ with $l' \in \llbracket l+1,k^*\rrbracket$ of an optimal solution $s^*$

• $t^*$ is the number of items trashed from $X^*$ in $s^*$, where $X^*=\llbracket q,q^*-1\rrbracket$

• Notice that in $s^*$ items of $X^*$ must by placed in $b^*_l$, $b_0^*$ or $T^*$. We mimic the optimal in the current call of the DP by packing $X^*$ in $b_l, b_0$ and T.

• To that end, the DP:

  • packs $q$ in $b_l$ (as required by the corresponding constraint of $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$),

  • packs the $t^*$ largest (in terms of $\overline{a}$) remaining items of $X^*$ to the trash

  • packs the remaining items of $X^*$ into $b_\ell$ until $\tilde{f}(b_\ell )>1$ or $X^* = \emptyset$

  • packs the remaining items of $X^*$ into $b_0$ until $X^* = \emptyset$

We discuss next where the other items (of $\llbracket q^*,n\rrbracket$) are packed. Notice that in $s^*$, bin $b^*_l$ may contain items of $\llbracket q^*,n\rrbracket$, and thus the DP may also have to pack items of $\llbracket q^*,n\rrbracket$ into $b_l$. The key is that the decision of which items of $\llbracket q^*,n\rrbracket$ to pack into $b_l$ is not taken at this step of the algorithm but only later (to avoid packing in $b_l$ items of large $\overline{a}$ value that are in the trash in $s^*$). To allow this decision to be taken later, let $\varDelta _b$ be the size of the empty space in $b_l$ after packing $X^*$ as described above, and let $b_0^{X^*}=b_0 \cap X^*$. After the previous steps, the DP makes a recursive call to get a solution $\tilde{s}$ that packs $\llbracket q^*,n\rrbracket$ into regular bins, the trash, and a dummy bin $\tilde{b}_0$. So far solution $\tilde{s}$ has not used any of the empty space $\varDelta _b$. However, we can unpack items from $\tilde{b}_0$ to $b_\ell$ while ensuring that these items do not deviate in $b_\ell$ (as all these items have index greater than q).

The formal description of $DP(q,t,\ell )$ and its correctness, stated formally in the following two results, are provided in [5].

Lemma 9

$\varvec{(\star ).}$ For any $\mathcal {I}$ input of $\textsc {G}\hbox {-}\varGamma \textsc {RBP}\hbox {-}\textsc {T}$, $DP(\mathcal {I})$ provides an almost feasible solution of cost at most $\textsf {OPT} (\mathcal {I})$.

Lemma 10

$\varvec{(\star ).}$ There is a 3-approximation for $\varGamma \textsc {RBP}$ with small values running in $\mathcal {O}(n^6log(n))$.

By Lemma 4, the following theorem is now immediate using a $\frac{3}{2}$-approximation for classical bin-packing (see for example in [16]) as a black box.

Theorem 5

There is a 4.5-approximation for $\varGamma \textsc {RBP}$ running in $\mathcal {O}(n^6log(n))$.