paperonly techreportonly

# Approximation Schemes for Multiperiod Binary Knapsack Problems

Zuguang Gao, John R. Birge, and Varun Gupta111All authors are with the
University of Chicago. Emails: {zuguang.gao, john.birge,
<EMAIL_ADDRESS>
###### Abstract

An instance of the multiperiod binary knapsack problem (MPBKP) is given by a
horizon length $T$, a non-decreasing vector of knapsack sizes
$(c_{1},\ldots,c_{T})$ where $c_{t}$ denotes the cumulative size for periods
$1,\ldots,t$, and a list of $n$ items. Each item is a triple $(r,q,d)$ where
$r$ denotes the reward or value of the item, $q$ its size, and $d$ denotes its
time index (or, deadline). The goal is to choose, for each deadline $t$, which
items to include to maximize the total reward, subject to the constraints that
for all $t=1,\ldots,T$, the total size of selected items with deadlines at
most $t$ does not exceed the cumulative capacity of the knapsack up to time
$t$. We also consider the multiperiod binary knapsack problem with soft
capacity constraints (MPBKP-S) where the capacity constraints are allowed to
be violated by paying a penalty that is linear in the violation. The goal of
MPBKP-S is to maximize the total profit, which is the total reward of the
selected items less the total penalty. Finally, we consider the multiperiod
binary knapsack problem with soft stochastic capacity constraints (MPBKP-SS),
where the non-decreasing vector of knapsack sizes $(c_{1},\ldots,c_{T})$
follow some arbitrary joint distribution but we are given access to the profit
as an oracle, and we must choose a subset of items to maximize the total
expected profit, which is the total reward less the total expected penalty.

For MPBKP, we exhibit a fully polynomial-time approximation scheme that
achieves $(1+\epsilon)$ approximation with runtime
$\tilde{\mathcal{O}}\left(\min\left\\{n+\frac{T^{3.25}}{\epsilon^{2.25}},n+\frac{T^{2}}{\epsilon^{3}},\frac{nT}{\epsilon^{2}},\frac{n^{2}}{\epsilon}\right\\}\right)$;
for MPBKP-S, the $(1+\epsilon)$ approximation can be achieved in
$\mathcal{O}\left(\frac{n\log
n}{\epsilon}\cdot\min\left\\{\frac{T}{\epsilon},n\right\\}\right)$. To the
best of our knowledge, our algorithms are the first FPTAS for any multiperiod
version of the Knapsack problem since its study began in 1980s. For MPBKP-SS,
we prove that a natural greedy algorithm is a $2$-approximation when items
have the same size. Our algorithms also provide insights on how other
multiperiod versions of the knapsack problem may be approximated.

##  1 Introduction

Knapsack problems are a classical category of combinatorial optimization
problems, and have been studied for more than a century (Mathews, , 1896).
They have found wide applications in various fields (Kellerer et al., , 2004),
such as selection of investments and portfolios, selection of assets, finding
the least wasteful way to cut raw materials, etc. One of the most commonly
studied problem is the so-called _0-1 knapsack problem_ , where a set of $n$
items are given, each with a reward and a size, and the goal is to select a
subset of these items to maximize the total reward, subject to the constraint
that the total size may not exceed some knapsack capacity. It is well-known
that the 0-1 knapsack problem is NP-complete. However, the problem was shown
to possess _fully polynomial-time approximation schemes (FPTASs)_ , i.e.,
there are algorithms that achieve $(1+\epsilon)$ factor of the optimal value
for any $\epsilon\in(0,1)$, and take polynomial time in $n$ and $1/\epsilon$.

The first published FPTAS for the 0-1 knapsack problem was due to Ibarra and
Kim,  (1975) where they achieve a time complexity
$\widetilde{\mathcal{O}}\left(n+(1/\epsilon^{4})\right)$ by dividing the items
into a class of “large” items and a class of “small” items. The problem is
first solved for large items only, using the dynamic program approach, with
rewards rounded down using some discretization quantum (chosen in advance),
and the small items are added later. Lawler,  (1979) proposed a more nuanced
discretization method to improve the polylogarithmic factors. Since then,
improvements have been made on the dynamic program for large items (Kellerer
and Pferschy, , 2004; Rhee, , 2015). Most recently, the FPTAS has been
improved to $\widetilde{\mathcal{O}}\left(n+(1/\epsilon)^{9/4}\right)$ in Jin,
(2019).

In this paper, we study three extensions of the 0-1 knapsack problem. First,
we consider a multiperiod version of the 0-1 knapsack problem, which we call
the _multiperiod binary knapsack problem (MPBKP)_. There is a horizon length
$T$ and a vector of knapsack sizes $(c_{1},\ldots,c_{T})$, where $c_{t}$ is
the cumulative size for periods $1,\ldots,t$ and is non-decreasing in $t$. We
are also given a list of $n$ items, each associated with a triple $(r,q,d)$
where $r$ denotes the reward or value of the item, $q$ its size, and $d$
denotes its time index (or, deadline). The goal is to choose a reward
maximizing set of items to include such that for any $t=1,\ldots,T$, the total
size of selected items with deadlines at most $t$ does not exceed the
cumulative capacity of the knapsack up to time $t$. The application that
motivates this problem is a seller who produces $(c_{t}-c_{t-1})$ units of a
good in time period $t$, and can store unsold goods for selling later. The
seller is offered a set of bids, where each bid includes a price ($r$), a
quantity demanded ($q$), and a time at which this quantity is needed. The
problem of deciding the revenue maximizing subset of bids to accept is exactly
MPBKP.

The second extension we consider is the _multiperiod binary knapsack problem
with soft capacity constraints (MPBKP-S)_ where at each period the capacity
constraint is allowed to be violated by paying a penalty that is linear in the
violation. The goal of MPBKP-S is then to maximize the total profit, which is
the total reward of the selected items less the total penalty. In this case,
the seller can procure goods from outside at a certain rate if his supply is
not enough to fulfill the bids he accepts, and wants to maximize his profit.

The third extension we consider is the _multiperiod binary knapsack problem
with soft stochastic capacity constraints (MPBKP-SS)_ where the non-decreasing
vector of knapsack sizes $(c_{1},\ldots,c_{T})$ follows some arbitrary joint
distribution given as the set of sample paths of the possible realizations and
their probabilities. We select the items _before_ realizations of any of these
random incremental capacities to maximize the total _expected_ profit, which
is the total reward of selected items less the total expected penalty. In this
case, the production of the seller at each time is random, but he has to
select a subset of bids before realizing his supply. Again, the seller can
procure capacity from outside at a certain rate if his realized supply is not
enough to fulfill the bids he accepts, and wants to maximize his expected
profit.

We note that MPBKP is also related to a number of other multiperiod versions
of the knapsack problem in literature. The multiperiod knapsack problem (MPKP)
proposed by Faaland,  (1981) has the same structure as MPBKP, except that in
Faaland,  (1981), each item can be repeated multiple times, i.e., the decision
variables for each item is not binary, but any nonnegative integer (in the
single-period case, this is called the unbounded knapsack problem (Andonov et
al., , 2000)). To the best of our knowledge, there has been no further studies
on MPKP since Faaland,  (1981). In the multiple knapsack problem (MKP), there
are $m$ knapsacks, each with a different capacity, and items can be inserted
to any knapsacks (subject to its capacity constraints). It has been shown in
Chekuri and Khanna,  (2005) that MKP does not admit an FPTAS, but an efficient
polynomial time approximation scheme (EPTAS) has been found in Jansen,
(2012), with runtime depending polynomially on $n$ but exponentially on
$1/\epsilon$. The incremental knapsack problem (IKP) is another multiperiod
version of the knapsack problem (Hartline and Sharp, , 2006), where the
knapsack capacity increases over time, and each selected item generates a
reward on every period after its insertion, but this reward is discounted over
time. Unlike MPBKP, items do not have deadlines and can be selected anytime
throughout the $T$ periods. A PTAS for the IKP when the discount factor is $1$
(time invariant, referred to as IIKP) and $T=\mathcal{O}\left(\sqrt{\log
n}\right)$ has been found in Bienstock et al.,  (2013), and it has been shown
that IIKP is strongly NP-hard. Later, Faenza and Malinovic,  (2018) proposed
the first PTAS for IIKP regardless of $T$, and Della Croce et al.,  (2019)
proposed an PTAS for IKP when $T$ is a constant. Most recent developments of
IKP include Aouad and Segev,  (2020); Faenza et al.,  (2020). Other similar
problems and/or further extensions include the multiple-choice multiperiod
knapsack problem (Randeniya, , 1994; Lin and Wu, , 2004; Lin and Chen, ,
2010), the multiperiod multi-dimensional knapsack problem (Lau and Lim, ,
2004), the multiperiod precedence-constrained knapsack problem (Moreno et al.,
, 2010; Samavati et al., , 2017), to name a few.

Our main contributions of this paper are two-fold. First, from the perspective
of model formulation, we propose the MPBKP and its generalized versions
MPBKP-S and MPBKP-SS. Despite the fact that there are a number of
multiperiod/multiple versions of knapsack problems, including those mentioned
above (many of which are strongly NP-hard), the MPBKP and MPBKP-S we proposed
here are the first to admit an FPTAS among any multiperiod versions of the
classical knapsack problem since their initiation back in 1980s. With these
results, it is thus interesting to see where the boundary lies between these
multiperiod problems that admit an FPTAS and those problems that do not admit
an FPTAS. Second, the algorithms we propose for both MPBKP and MPBKP-S are
generalized from the ideas of solving 0-1 knapsack problems, but with
nontrivial modifications as we will address in the following sections. For
MPBKP-SS, we propose a greedy algorithm that achieves $2$-approximation for
the special case when all items have the same size.

The rest of this paper is organized as follows. In Section 2 we formally write
the three problems in mathematical programming form. The FPTAS for MPBKP is
proposed in Section 3 and the FPTAS for MPBKP-S is proposed in Section 4.
Alternative algorithms for both problems are also provided in Apendix. A
greedy algorithm for a special case of MPBKP-SS is proposed in Section 5. All
proofs are left to Appendix but we provide proof ideas in the main body.

##  2 Problem Formulation and Main Results

In this section, we formally introduce the Multiperiod Binary Knapsack Problem
(MPBKP), as well as the generalized versions: the Multiperiod Binary Knapsack
Problem with Soft capacity constraints (MPBKP-S), and Multiperiod Binary
Knapsack Problem with Soft Stochastic Capacity constraints (MPBKP-SS).

###  2.1 Multiperiod binary Knapsack problem (MPBKP)

An instance of MPBKP is given by a set of $n$ items, each associated with a
triple $(r_{i},q_{i},d_{i})$, and a sequence of knapsack capacities
$\\{c_{1},\ldots,c_{T}\\}$. For each item $i$, we get reward $r_{i}$ if and
only if $i$ is included in the knapsack by time $d_{i}$. We assume that
$r_{i}\in\mathbb{N}$, $q_{i}\in\mathbb{N}$ and
$d_{i}\in[T]:=\\{1,\ldots,T\\}$. The knapsack capacity at time $t$ is $c_{t}$,
and by convention $c_{0}=0$. The MPBKP can be written in the integer program
(IP) form:

$\displaystyle\max_{x}z=\sum_{i=1}^{n}r_{i}x_{i}$ (1a) $\displaystyle\text{
s.t. }\sum_{j:d_{j}\leq t}q_{j}x_{j}\leq c_{t},\quad\forall t=1,\ldots,T$ (1b)
$\displaystyle\qquad x_{i}\in\\{0,1\\},\quad\forall i=1,\ldots,n$ (1c)

where $x_{i}$’s are binary decision variables, i.e., $x_{i}$ is $1$ if item
$i$ is included in the knapsack and is $0$ otherwise. In (1), we aim to pick a
subset of items to maximize the objective function, which is the total reward
of picked items, subject to the constraints that by each time $t$, the total
size of picked items with deadlines up to $t$ does not exceed the knapsack
capacity at time $t$, which is $c_{t}$. For each $t\in[T]$, let
$\mathcal{I}(t):=\\{i\in[n]\mid d_{i}=t\\}$ denote the set of items with
deadline $t$. Note that without loss of generality, we may assume that
$\mathcal{I}(t)\neq\emptyset,\forall t$ and $c_{t}>0$. We further note that
the decision variables $x_{i}$’s in (1) are binary, but if we relax this to
any nonnegative integers, the problem becomes the so-called multiperiod
knapsack problem (MPKP) as in Faaland,  (1981). Our first main result is the
following theorem on MPBKP.

######  Theorem 1.

An FPTAS exists for MPBKP. Specifically, there exists a deterministic
algorithm that achieves $(1+\epsilon)$-approximation in
$\tilde{\mathcal{O}}\left(\min\left\\{n+\frac{T^{3.25}}{\epsilon^{2.25}},n+\frac{T^{2}}{\epsilon^{3}},\frac{nT}{\epsilon^{2}},\frac{n^{2}}{\epsilon}\right\\}\right)$.

As we will see shortly, MPBKP can be viewed as a special case of MPBKP-S. In
Section 3, we will provide an approximation algorithm for MPBKP with runtime
$\tilde{\mathcal{O}}\left(n+\frac{T^{3.25}}{\epsilon^{2.25}}\right)$. An
alternative algorithm with runtime
$\tilde{\mathcal{O}}\left(n+\frac{T^{2}}{\epsilon^{3}}\right)$ is provided in
Appendix B. In Section 4, we will provide an approximation algorithm for
MPBKP-S with runtime $\tilde{O}\left(\frac{nT}{\epsilon^{2}}\right)$, which is
also applicable to MPBKP.

###  2.2 Multiperiod binary Knapsack problem with soft capacity constraints
(MPBKP-S)

In MPBKP-S, the capacity constraints in (1) no longer exist, i.e., the total
size of selected items at each time step is allowed to be greater than the
total capacity up to that time, however, there is a penalty rate
$B_{t}\in\mathbb{N}$ for each unit of overflow at period $t$. We assume that
$B_{t}>\max_{i\in[n]:d_{i}\leq t}\frac{r_{i}}{q_{i}}$ to avoid trivial cases
(any item with $\frac{r_{i}}{q_{i}}\geq B_{t}$ and $d_{i}\leq t$ will always
be added to generate more profit). In the IP form, MPBKP-S can be written as

$\displaystyle\max_{x,y}\sum_{i\in[n]}r_{i}x_{i}-\sum_{t=1}^{T}B_{t}y_{t}$
(2a) $\displaystyle\text{s.t.
}\sum_{i\in\mathcal{I}(1)\cup\cdots\cup\mathcal{I}(t)}q_{i}x_{i}-\sum_{s=1}^{t}y_{s}\leq
c_{t},\quad\forall t:1\leq t\leq T$ (2b) $\displaystyle\qquad
x_{i}\in\\{0,1\\},\quad y_{t}\geq 0,$ (2c)

where the decision variables $y_{t},t=1,\ldots,T$ represent the units of
overflow at time $t$, and $c_{t}-c_{t-1}$ is the incremental capacity at time
$t$. The objective is to choose a subset of the $n$ items to maximize the
total profit, which is the sum of the rewards of the selected items minus the
sum of penalty paid at each period, and the constraints enforce that the total
size of accepted items by the end of each period must not exceed the sum of
the cumulative capacity and the units of overflow. Our second main result is
the following theorem on MPBKP-S.

######  Theorem 2.

An FPTAS exists for MPBKP-S. Specifically, there exists an algorithm which
achieves $(1+\epsilon)$-approximation in ${\mathcal{O}}\left(\frac{n\log
n}{\epsilon}\cdot\min\left\\{\frac{T}{\epsilon},n\right\\}\right)$.

In section 4 we will present an approximation algorithm for solving MPBKP-S
with time complexity $\mathcal{O}\left(\frac{nT\log n}{\epsilon^{2}}\right)$.
An alternative FPTAS with runtime
$\mathcal{O}\left(\frac{n^{2}}{\epsilon}\right)$ is provided in Appendix C.
For the ease of presentation, our algorithms and analysis are presented for
the case $B_{t}=B$, but they can be generalized to the heterogeneous
$\\{B_{1},\ldots,B_{T}\\}$ in a straightforward manner. It is worth noting
that the algorithm for MPBKP that we introduce in section 3 does not extend to
MPBKP-S, and we will make this clear in the beginning of section 4.

###  2.3 Multiperiod Binary Knapsack Problem with Soft Stochastic Capacity
Constraints (MPBKP-SS)

The MPBKP-SS formulation is similar to (2), except that the vector of knapsack
sizes $(c_{1},\ldots,c_{T})$ follows some arbitrary joint distribution given
to the algorithm as the set of possible sample path (realization) of knapsack
sizes and the probability of each sample path. We use $\omega$ to index sample
paths which we denote by $\\{c_{t}(\omega)\\}$, $p(\omega)$ as the probability
of sample path $\omega$, and $\Omega$ as the set of possible sample paths. The
goal is to pick a subset of items before the realization of $\omega$ so as to
maximize the expected total profit, which is the sum of the rewards of the
selected items deducted by the total (expected) penalty. For a sample
$\omega\in\Omega$ let $y_{t}(\omega)$ be the overflow at time $t$. Then, we
can write the problem in IP form as:

$\displaystyle\max_{x,y}\sum_{i\in[n]}r_{i}x_{i}-\mathbb{E}_{\omega}\left[B_{t}\cdot\sum_{t=1}^{T}y_{t}(\omega)\right]$
(3a) $\displaystyle\text{s.t.
}\sum_{i\in\mathcal{I}(1)\cup\cdots\cup\mathcal{I}(t)}q_{i}x_{i}-\sum_{s=1}^{t}y_{s}(\omega)\leq
c_{t}(\omega),\quad\forall\omega\in\Omega,1\leq t\leq T$ (3b)
$\displaystyle\qquad x_{i}\in\\{0,1\\},\quad y_{t}\geq 0$ (3c)

Our third main result is the following theorem on MPBKP-SS, which asserts a
greedy algorithm for the special case when all items are of the same size.
Details will be provided in Section 5.

######  Theorem 3.

If $q_{i}=q$ for all $i\in[n]$, then there exists a greedy algorithm that
achieves $2$-approximation for MPBKP-SS in
$\mathcal{O}\left(n^{2}T|\Omega|\right)$.

We further note that both MPBKP-S and MPBKP-SS are special cases of non-
monotone submodular maximization which is _not_ non-negative, for which not
many general approximations are known. In that sense, studying these problems
would be an interesting direction to develop techniques for it.

##  3 FPTAS for MPBKP

In this section, we provide an FPTAS for the MPBKP with time complexity
$\tilde{\mathcal{O}}\left(n+\frac{T^{3.25}}{\epsilon^{2.25}}\right)$. We will
apply the “functional approach” as used in Chan,  (2018). The main idea is to
use the results on function approximations (Chan, , 2018; Jin, , 2019) as
building blocks – for each period we approximate one function that gives, for
every choice of available capacity, the maximum reward obtainable by selecting
items in that period. We then combine “truncated” version of these functions
using $(\max,+)$-convolution. This idea, despite its simplicity, allows us to
obtain an FPTAS for MPBKP. Such a result should not be taken as granted – as
we will see in the next section, this method does not apply for MPBKP-S, even
though it is just a slight generalization of MPBKP.

We begin with some preliminary definitions and notations. For a given set of
item rewards and sizes,
$\mathcal{I}=\\{(r_{1},q_{1}),\ldots,(r_{n^{\prime}},q_{n^{\prime}})\\}$,
define the function

$\displaystyle
f_{\mathcal{I}}(c):=\max_{x_{1},\ldots,x_{n^{\prime}}}\left\\{\sum_{i\in\mathcal{I}}r_{i}x_{i}\
:\ \sum_{i\in\mathcal{I}}q_{i}x_{i}\leq c,\
x_{1},\ldots,x_{n^{\prime}}\in\\{0,1\\}\right\\}$ (4)

for all $c\geq 0$, and $f_{\mathcal{I}}(c):=-\infty$ for $c<0$. The function
$f_{\mathcal{I}}$ is a nondecreasing step function, and the number of steps is
called the _complexity_ of that function. Further, for any
$\mathcal{I}=\mathcal{I}_{1}\sqcup\mathcal{I}_{2}$, i.e., $\mathcal{I}$ being
a disjoint union of $\mathcal{I}_{1}$ and $\mathcal{I}_{2}$, we have that
$f_{\mathcal{I}}=f_{\mathcal{I}_{1}}\oplus f_{\mathcal{I}_{2}}$, where
$\oplus$ denotes the $(\max,+)$-_convolution_ : $(f\oplus
g)(c)=\max_{c^{\prime}\in\mathbb{R}}\left(f(c^{\prime})+g(c-c^{\prime})\right)$.

We define the _truncated function_ $f_{\mathcal{I}}^{c^{\prime}}$ as follows:

$\displaystyle
f_{\mathcal{I}}^{c^{\prime}}(c)=\begin{cases}f_{\mathcal{I}}(c)&c\leq
c^{\prime},\\\ -\infty&c>c^{\prime}.\end{cases}$ (5)

Recall that we denote the set of items with deadline $t$ by $\mathcal{I}(t)$.
We next define the function $f_{t}$ as follows:

$\displaystyle f_{t}:=\begin{cases}f_{\mathcal{I}(1)}^{c_{1}}&t=1,\\\
\left(f_{t-1}\oplus f_{\mathcal{I}(t)}\right)^{c_{t}}&t\geq 2.\end{cases}$ (6)

In words, each function value of $f_{t}(c)$ corresponds to a feasible, in fact
an optimal, solution $x$ for items with deadline at most $t$ as the next
proposition shows.

######  Proposition 1.

Let $x^{*}$ be the optimal solution for MPBKP (1). We have that the optimal
value of (1), $\sum_{i\in[n]}r_{i}x_{i}^{*}$, satisfies
$\sum_{i\in[n]}r_{i}x_{i}^{*}=f_{T}(c_{T}).$

Proposition 1 implies that, to obtain an approximately optimal solution for
MPBKP (1), it is sufficient to have a good approximation for the function

$\displaystyle f_{T}=\left(\cdots\left(\left(f_{\mathcal{I}(1)}^{c_{1}}\oplus
f_{\mathcal{I}(2)}\right)^{c_{2}}\oplus
f_{\mathcal{I}(3)}\right)^{c_{3}}\cdots\oplus
f_{\mathcal{I}(T)}\right)^{c_{T}}.$ (7)

We say that a function $\tilde{f}$ approximates the nonnegative function $f$
with factor $1+\epsilon$ if $\tilde{f}(c)\leq
f(c)\leq(1+\epsilon)\tilde{f}(c)$ for all $c\in\mathbb{R}$. It should be clear
that if $\tilde{f}$ approximates $f$ with factor $1+\epsilon$ and $\tilde{g}$
approximates $g$ with factor $1+\epsilon$, then $\tilde{f}\oplus\tilde{g}$
approximates $f\oplus g$ with factor $1+\epsilon$. We then introduce the
following result from Jin,  (2019) for 0-1 Knapsack problem.

######  Lemma 1 (Jin,  (2019)).

Given a set $\mathcal{I}=\\{(r_{1},q_{1}),\ldots,(r_{n},q_{n})\\}$, we can
obtain $\tilde{f}_{\mathcal{I}}$ that approximates $f_{\mathcal{I}}$ (defined
in (4)) with factor $1+\epsilon$ and complexity
$\tilde{O}\left(\frac{1}{\epsilon}\right)$ in
$\tilde{O}\left(n+\left(1/\epsilon\right)^{2.25}\right)$.

With the above lemma, we present Algorithm 1 for MPBKP.

Algorithm 1 FPTAS for MPBKP

1:Input: $\epsilon,[n],c_{1},\ldots,c_{T}$ $\triangleright$ Set of items to be
packed, cumulative capacities

2:Output: $\tilde{f}_{t}$ $\triangleright$ Approximation of function $f_{t}$

3:Discard all items with $r_{i}\leq\frac{\epsilon}{n}\max_{j}r_{j}$ and
relabel the items

4:$r_{0}\leftarrow\min_{i}r_{i}$ $\triangleright$ Lower bound of solution
value

5:$m\leftarrow\left\lceil\log_{1+\epsilon}\frac{n^{2}}{\epsilon}\right\rceil$
$\triangleright$ number of distinct rewards to be considered, each in the form
$r_{0}\cdot(1+\epsilon)^{k}$

6:Obtain $\tilde{f}_{\mathcal{I}(1)}$ that approximates $f_{\mathcal{I}(1)}$
with factor $(1+\epsilon)$ using Lemma 1

7:$\tilde{f}_{1}:=\tilde{f}_{\mathcal{I}(1)}^{c_{1}}$ $\triangleright$
$\tilde{f}_{1}$ has complexity at most
$m=\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$

8:for $t=2,\ldots,T$ do

9: Obtain $\tilde{f}_{\mathcal{I}(t)}$ that approximates $f_{\mathcal{I}(t)}$
with factor $(1+\epsilon)$ using Lemma 1

10: $l\leftarrow$ complexity of $\tilde{f}_{\mathcal{I}(t)}$ $\triangleright$
$l=\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$

11: Compute (all breakpoints and their values of)
$\hat{f}_{t}:=\left(\tilde{f}_{t-1}\oplus\tilde{f}_{\mathcal{I}(t)}\right)^{c_{t}}$,
taking $m\cdot l$ time $\triangleright$ $\hat{f}_{t}$ has complexity
$\tilde{\mathcal{O}}\left(\frac{1}{\epsilon^{2}}\right)$

12:
$\tilde{f}_{t}:=r_{0}\cdot(1+\epsilon)^{\left\lfloor\log_{1+\epsilon}\left(\frac{\hat{f}_{t}}{r_{0}}\right)\right\rfloor}$
$\triangleright$ Round $\hat{f}_{t}$ down to the nearest
$r_{0}\cdot(1+\epsilon)^{k}$. Now $\tilde{f}_{t}$ has complexity at most
$m=\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$

13:end for

We now describe the intuition behind Algorithm 1. We first discard all items
with reward $r_{i}\leq\frac{\epsilon}{n}\max_{j}r_{j}$. The maximum we could
lose is $n\cdot\frac{\epsilon}{n}\max_{j}r_{j}=\epsilon\max_{j}r_{j}$, which
is at most $\epsilon$ fraction of the optimal value. We next obtain all
$\tilde{f}_{\mathcal{I}(t)}$, for all $t=1,\ldots,T$, that approximate
$f_{\mathcal{I}(t)}$ (as defined in (4)) within a $(1+\epsilon)$ factor. These
functions $\tilde{f}_{\mathcal{I}(t)}$ have complexity
$\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$. We start with combining
the functions of period $1$ and period $2$ using $(\max,+)$-convolution. To
enforce the constraint that the total size of selected items in period $1$
does not exceed the capacity of period $1$, we truncate
$\tilde{f}_{\mathcal{I}(1)}$ by $c_{1}$ (so that any solution using more
capacity in period $1$ results in $-\infty$ reward) and do the convolution on
the truncated function $\tilde{f}_{1}$. Since both functions are step
functions with complexity
$\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$, the $(\max,+)$
convolution can be done in time
$\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right)$. The resulting function
$\hat{f}_{2}$ would have complexity
$\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right)$. To avoid inflating the
complexity throughout different periods (which increases computation
complexity), the function $\hat{f}_{2}$ is rounded down to the nearest
$r_{0}\cdot(1+\epsilon)^{k}$, where $r_{0}:=\min_{j}r_{j}$ and $k$ is some
nonnegative integer. Note that $r_{0}$ is a lower bound of any solution value.
After discarding small-reward items, we have that
$\frac{\max_{j}r_{j}}{r_{0}}\leq\frac{n}{\epsilon}$, which implies that
$n\max_{j}r_{j}=\frac{n^{2}}{\epsilon}r_{0}$ is an upper bound for the optimal
solution value. Therefore, after rounding down the function values of
$\hat{f}_{2}$ and obtaining $\tilde{f}_{2}$, there are at most
$\log_{1+\epsilon}\frac{n^{2}}{\epsilon}\approx\frac{1}{\epsilon}\log\frac{n^{2}}{\epsilon}$
different values on $\tilde{f}_{2}$. Now we have brought down the complexity
of $\tilde{f}_{2}$ again to
$\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$, at an additional
$(1+\epsilon)$ factor loss in the approximation error. We then move to period
$3$ and continue this pattern of $(\max,+)$-convolution, truncation, and
rounding down. In the end when we reach period $T$, $\tilde{f}_{T}$ will only
contain feasible solutions to (1), and approximate $f_{T}$ with total
approximation factor of $(1+\epsilon)^{T}\approx(1+T\epsilon)$. Formally, we
have the following lemma which shows the approximation factor of
$\tilde{f}_{t}$ for $f_{t}$.

######  Lemma 2.

Let $\tilde{f}_{t}$ be the functions obtained from Algorithm 1, and let
$f_{t}$ be defined as in (6). Then, $\tilde{f}_{t}$ approximates $f_{t}$ with
factor $(1+\epsilon)^{t}$, i.e., $\tilde{f}_{t}(c)\leq
f_{t}(c)\leq(1+\epsilon)^{t}\tilde{f}_{t}(c)$ for all $0\leq c\leq c_{t}$.

Lemma 2 and Proposition 1 together imply that $\tilde{f}_{T}(c_{T})$, obtained
from Algorithm 1, approximates the optimal value of MPBKP (1) by a factor of
$(1+\epsilon)^{T}\approx(1+T\epsilon)$. In Algorithm 1, obtaining
$\tilde{f}_{\mathcal{I}(t)}$ for all $t=1,\ldots,T$ takes time
$\tilde{O}\left(n+{T}/{\epsilon^{2.25}}\right)$; computing the
$(\max,+)$-convolution on $\tilde{f}_{t-1}\oplus\tilde{f}_{\mathcal{I}(t)}$
for all $t$ take time $T\cdot m\cdot l=\tilde{O}\left(T/\epsilon^{2}\right)$.
Therefore, Algorithm 1 has runtime
$\tilde{O}\left(n+T/\epsilon^{2.25}\right)$. As a result, we have the
following proposition.

######  Proposition 2.

Taking $\epsilon^{\prime}=T\epsilon$, Algorithm 1 achieves
$(1+\epsilon^{\prime})$-approximation for MPBKP in
$\tilde{O}\left(n+\frac{T^{3.25}}{{\epsilon^{\prime}}^{2.25}}\right)$.

##  4 FPTAS for MPBKP-S

In this section, we provide an FPTAS for the MPBKP-S with time complexity
$\mathcal{O}\left(\frac{Tn\log n}{\epsilon^{2}}\right)$. An alternative FPTAS
with time complexity $\mathcal{O}\left(\frac{n^{2}\log n}{\epsilon}\right)$ is
provided in Appendix C. Combining the two, we show that our algorithms achieve
$(1+\epsilon)$ approximation ratio in time $\mathcal{O}\left(\frac{n\log
n}{\epsilon}\cdot\min\left\\{\frac{T}{\epsilon},n\right\\}\right)$, which
proves Theorem 2. We should note that the algorithm in the previous section
does not apply here: we could similarly define a function which gives the
maximum profit ($=$reward$-$penalty) under a given capacity constraint, but
the main obstacle is on the $(\max,+)$-convolution because profit does not
“add up”. In other words, the total profit we earn by selecting items in the
set ${\mathcal{S}}_{1}\cup{\mathcal{S}}_{2}$ is not the sum of the profits we
earned by selecting ${\mathcal{S}}_{1}$ and ${\mathcal{S}}_{2}$ separately.
For this reason, we can no longer rely on the techniques used in function
approximation and $(\max,+)$-convolution as in Chan,  (2018); Jin,  (2019).
Instead, our main idea is motivated by the techniques that originated from
earlier papers (Ibarra and Kim, , 1975; Lawler, , 1979), but adapting their
technique to MPBKP-S requires significant modifications as we show in this
section. We restrict our presentation to the case $B_{t}=B$ for readability,
but our algorithms and analysis generalize in a straightforward manner when
the penalties for buying capacity are heterogeneous $\\{B_{1},\ldots,B_{T}\\}$
(by replacing $B$ with $\min_{\tau\leq t}B_{\tau}$ in the calculations of
profit/penalty at period $t$ on line 7 of Algorithm 2).

Preliminaries: We first introduce some notation. From now on, let
$\mathcal{R}({\mathcal{S}}):=\sum_{i\in{\mathcal{S}}}r_{i}$. The optimal
solution set to (2) is denoted by $\mathcal{S}^{*}$. The total profit earned
can be expressed as a function of the solution set $\mathcal{S}$:

$\displaystyle\mathcal{P}(\mathcal{S})=\mathcal{R}({\mathcal{S}})-B\cdot\sum_{t=1}^{T}\left[\sum_{j\in{\mathcal{S}}\cap\mathcal{I}(t)}q_{j}-\max\left\\{c_{t}-\sum_{j\in{\mathcal{S}},d_{j}\leq
t}q_{j},\ c_{t}-c_{t-1}\right\\}\right]^{+}.$ (8)

Let $p_{i}$ be the profit of item $i$, which is defined as the profit earned
if we select only $i$, i.e.,
$p_{i}=r_{i}-B\cdot\left(q_{i}-c_{d_{i}}\right)^{+}$. Without loss of
generality, we assume that each item $i$ is by itself profitable, i.e.,
$p_{i}\geq 0$, so one profitable solution would be $\\{i\\}$. Let
$P:=\max_{i}p_{i}$ and $\bar{P}:=\sum_{i\in[n]}p_{i}$. The following bounds on
$\mathcal{P}({\mathcal{S}}^{*})$ follow:

$\displaystyle P\leq\mathcal{P}(\mathcal{S}^{*})\leq\bar{P}\leq nP.$ (9)

Partition of items: We partition the set of items $[n]$ into two sets: a set
of “large” items $\mathcal{I}_{L}$ and a set of “small” items
$\mathcal{I}_{S}$ such that we can bound the number of large items in any
optimal solution. The main idea is to use dynamic programming to pick the
large items in the solution, and a greedy heuristic for ‘padding’ this partial
solution with small items. The criterion for small and large items is based on
balancing the permissible error $\epsilon\mathcal{P}({\mathcal{S}}^{*})$
equally in filling large items and filling small items. Instead of first
packing all large items and then all small items, we consider items in the
order of their deadlines, and for each deadline $t$, the large items are
selected first and then the small items are selected greedily in order of
their reward densities. As a result, the approximation error due to large
items overall will be $\frac{1}{2}\epsilon\mathcal{P}({\mathcal{S}}^{*})$ and
the error due to the small items with each deadline will be
$\frac{1}{2T}\epsilon\mathcal{P}({\mathcal{S}}^{*})$. This gives a total
approximation error of
$\frac{1}{2}\epsilon\mathcal{P}({\mathcal{S}}^{*})+T\cdot\frac{1}{2T}\epsilon\mathcal{P}({\mathcal{S}}^{*})=\epsilon\mathcal{P}({\mathcal{S}}^{*})$.

Suppose that we can find some $P_{0}$ that satisfies (10).

$\displaystyle P_{0}\leq\mathcal{P}(\mathcal{S}^{*})\leq 2P_{0}.$ (10)

Then, the set of items is partitioned as follows.

$\displaystyle\mathcal{I}_{L}:=\left\\{i\in[n]\mid
p_{i}\geq\frac{1}{2T}\epsilon
P_{0}\right\\};\qquad\mathcal{I}_{S}:=\left\\{i\in[n]\mid
p_{i}<\frac{1}{2T}\epsilon P_{0}\right\\}.$ (11)

This partition is computed in $\mathcal{O}(n)$ time and is not the dominant
term in time complexity. Let $n_{L}=|\mathcal{I}_{L}|$ and
$n_{S}=|\mathcal{I}_{S}|$, so that $n_{L}+n_{S}=n$. Further, let

$\displaystyle\mathcal{I}_{L}(t):=\left\\{i\in{\mathcal{S}}_{L}\mid
d_{i}=t\right\\},\quad\mbox{and}\quad\mathcal{I}_{S}(t):=\left\\{i\in{\mathcal{S}}_{S}\mid
d_{i}=t\right\\}$

denote the set of large and small items, respectively, with deadline $t$. We
will assume that the items in $\mathcal{I}_{L}$ are indexed in non-decreasing
order of their deadlines, i.e., $\forall i,j\in\mathcal{I}_{L}$ such that
$j\geq i$, we have that $d_{i}\leq d_{j}$. Denote by $I_{L}(t)$ as the index
of the last item with deadline $t$, i.e.,
$I_{L}(t):=\max_{i\in{\mathcal{S}}_{L}\cap\mathcal{I}_{L}(t)}i$. For each time
$t$, we will also sort the small items in $\mathcal{I}_{S}(t)$ according to
their reward densities, i.e., $\forall i<j$ and $i,j\in\mathcal{I}_{S}(t)$,
$\frac{r_{i}}{q_{i}}\geq\frac{r_{j}}{q_{j}}$. This sorting only takes place
once for each guess $P_{0}$, and does not affect our overall time complexity
result.

Algorithm 2 DP on large items for MPBKP-S

1:Input: $\ \mathcal{I}_{L},\Delta c,$ $\triangleright$ Set of (large) items
to be packed, additional capacity available for packing

2: $\widetilde{A}(p)$ for all
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$
$\triangleright$ A set of partial solutions

3:Output: $\hat{A}(I_{L},p)$ for all
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$
$\triangleright$ Set of partial solutions after packing $\mathcal{I}_{L}$

4:Initialize $\forall p\ :\ \hat{A}(0,p):=\widetilde{A}(p)+\Delta c$

5:for $i=1,\ldots,I_{L}$ do

6: for
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$
do

7: $\hat{A}(i,p):=\hat{A}(i-1,p)$ $\triangleright$ If reject item $i$

8: end for

9: for
$\bar{p}=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$
do

10: ${p}=\bar{p}+\hat{r}_{i}-\left\lceil
B\left(q_{i}-{\color[rgb]{0,0,0}\max\left\\{0,\hat{A}(i-1,\bar{p})\right\\}}\right)^{+}\right\rceil_{\kappa}$

11:
$\hat{A}(i,p)=\max\left\\{\hat{A}(i,p),\hat{A}(i-1,\bar{p})-q_{i}\right\\}$
$\triangleright$ Accept $i$

12: end for

13: for
$p=\left\\{\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil-1,\ldots,1\right\\}\cdot\kappa$
do

14: if $\hat{A}(i,p-\kappa)<\hat{A}(i,p)$ then

15: $\hat{A}(i,p-\kappa)=\hat{A}(i,p)$

16: end if

17: end for

18:end for

Algorithm 3 Greedy on small items for MPBKP-S

1:Input: $\ \mathcal{I}_{S}$, $\hat{A}(p)$ for all
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$.
$\triangleright$ Set of (small) items to be packed, a set of partial solutions

2:Output: $\widetilde{A}(p)$ for all
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$
$\triangleright$ Set of partial solutions after packing $\mathcal{I}_{S}$

3:Initialize $\forall p\ :\ \widetilde{A}(p)=\hat{A}(p)$

4:for
$\bar{p}=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$
do

5:// Filter out small items with size larger than $\hat{A}(p)$

6: $\widetilde{\mathcal{I}}_{S}\leftarrow\emptyset$

7: for $i\in\mathcal{I}_{S}$ do

8: if $\hat{A}(\bar{p})\geq q_{i}$ then

9:
$\widetilde{\mathcal{I}}_{S}\leftarrow\widetilde{\mathcal{I}}_{S}\cup\\{i\\}$

10: end if

11: end for

12: $\tilde{\mathcal{R}}_{0^{\prime}}=0,\tilde{q}_{0^{\prime}}=0$, and relabel
the items in $\widetilde{\mathcal{I}}_{S}$ as
$\left\\{1^{\prime},\ldots,|\widetilde{\mathcal{I}}_{S}|^{\prime}\right\\}$
(in decreasing order of reward density)

13: for $i^{\prime}=1^{\prime},\ldots,|\widetilde{\mathcal{I}}_{S}|^{\prime}$
do

14:
$\tilde{\mathcal{R}}_{i^{\prime}}=\tilde{\mathcal{R}}_{(i-1)^{\prime}}+r_{i^{\prime}}$

15: $\tilde{q}_{i^{\prime}}=\tilde{q}_{(i-1)^{\prime}}+q_{i^{\prime}}$

16: end for

17: // Add small items using Greedy algorithm

18: for $i^{\prime}=1^{\prime},\ldots,|\widetilde{\mathcal{I}}_{S}|^{\prime}$
do

19: if $\tilde{q}_{i^{\prime}}\leq\hat{A}(\bar{p})$ then

20:
$p=\left\lfloor\bar{p}+\tilde{\mathcal{R}}_{i^{\prime}}\right\rfloor_{\kappa}$

21:
$\widetilde{A}({p})=\max\left\\{\widetilde{A}(p),\hat{A}(\bar{p})-\tilde{q}_{i^{\prime}}\right\\}$

22: end if

23: end for

24:end for

Algorithm 4 DP on large items and Greedy on small items for MPBKP-S

1:Define $\kappa=\frac{\epsilon^{2}P_{0}}{8T}$

2:Define $\hat{r}_{i}=\left\lfloor{r_{i}}\right\rfloor_{\kappa}$
$\triangleright$ Round down reward

3:// $\widetilde{A}_{t}(p)=$ leftover capacity for the algorithm’s partial
solution when earning (rounded) profit $p$ using items with deadlines at most
$t$ (small and large)

4:// $\hat{A}_{t}(p)=$ capacity left for the algorithm’s partial solution when
earning (rounded) profit $p$ by selecting large items in $\mathcal{I}_{L}(t)$
with rounded down rewards $\hat{r}$, given the partial solutions
$\widetilde{A}_{t-1}(p)$

5:Initialize $\hat{A}(0,p)=\widetilde{A}_{0}(p)=\begin{cases}0&p=0,\\\
-\infty&p>0.\end{cases}$

6:for $t=1,\ldots,T$ do

7: Run Algorithm 2 with $\mathcal{I}_{L}=\mathcal{I}_{L}(t),\Delta
c=c_{t}-c_{t-1}$, and $\widetilde{A}(p)=\widetilde{A}_{t-1}(p)$ for all
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$,
and obtain $\hat{A}_{t}(p):=\hat{A}(I_{L},p)$ for all $p$.

8: Run Algorithm 3 with $\mathcal{I}_{S}=\mathcal{I}_{S}(t)$ and
$\hat{A}(p)=\hat{A}(I_{L}(t),p)$ for all
$p=\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$,
and obtain $\widetilde{A}_{t}(p):=\widetilde{A}(p)$ for all $p$.

9:end for

Algorithm 5 FPTAS for MPBKP-S in $\mathcal{O}(Tn\log n/\epsilon^{2})$

1:$P_{0}\leftarrow{\bar{P}}$

2:$p^{*}\leftarrow 0$

3:while $p^{*}<(1-\epsilon)P_{0}$ do

4: $P_{0}\leftarrow\frac{P_{0}}{2}$

5: Run Algorithm 4 with the current $P_{0}$.

6:
$p^{*}\leftarrow\max_{\left\\{\begin{subarray}{c}p\in\left\\{0,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa\\\
\widetilde{A}_{T}(p)>-\infty\end{subarray}\right\\}}p$

7:end while

Algorithm overview: Our FPTAS algorithm is given in Algorithm 5 which uses a
doubling trick to guess the value of $P_{0}$ satisfying (10), and for each
guess uses Algorithm 4 as a subroutine. Algorithm 4 is the main algorithm for
MPBKP-S, which first selects the items with deadline $1$, then the items with
deadline $2$, and so on. For each deadline $t$, we maintain two sets of
partial solutions: the first, $\widetilde{A}_{t}(p)$, corresponds to an
approximately optimal (in terms of leftover capacity carried forward to time
$t+1$) subset of large and small items with deadline at most $t$ and some
_rounded profit_ $p$ ; and the second $\hat{A}_{t}(p)$ corresponds to the
optimal appending of large items with deadline $t$ to the approximately
optimal set of solutions corresponding to $\widetilde{A}_{t-1}$.

Given $\widetilde{A}_{t-1}$, we first select large items from
$\mathcal{I}_{L}(t)$ using dynamic programming to obtain $\hat{A}_{t}$, which
is done in Algorithm 2. In other words, given the partial solutions
$\widetilde{A}_{t-1}(\bar{p})$ for all
$\bar{p}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$,
$\hat{A}_{t}(p)$ is the maximum capacity left when earning _rounded profit_
(precise definition given in (A.2)) $p$ by adding items in
$\mathcal{I}_{L}(t)$. We then use a greedy heuristic to pick small items from
$\mathcal{I}_{S}(t)$ to obtain $\widetilde{A}_{t}$, which is done in Algorithm
3. Specifically, our goal in Algorithm 3 is to obtain the partial solutions
$\widetilde{A}_{t}(\cdot)$ given the partial solutions $\hat{A}_{t}(\cdot)$ by
packing the small items $\mathcal{I}_{S}(t)$. We initialize
$\widetilde{A}_{t}(\bar{p})$ with $\hat{A}_{t}(\bar{p})$, and for each
$\bar{p}$ we try to augment the solution corresponding to
$\hat{A}_{t}(\bar{p})$ using a subset
$\widetilde{\mathcal{I}}_{S}(t)\subseteq\mathcal{I}_{S}(t)$ defined as

$\widetilde{\mathcal{I}}_{S}(t):=\\{i\in\mathcal{I}_{S}(t)\mid
q_{i}\leq\hat{A}_{t}(\bar{p})\\}.$

The small items in $\widetilde{\mathcal{I}}_{S}(t)$ are sorted according to
their reward densities, and are added to the solution of
$\hat{A}_{t}(\bar{p})$ one by one. After each addition of a small item, if the
new total rounded reward is ${p}$, we compare the leftover capacity with
current $\widetilde{A}_{t}({p})$, and update $\widetilde{A}_{t}({p})$ with the
new solution if it has more leftover capacity. We continue this add-and-
compare (and possibly update) until we reach the situation where adding the
next small item overflows the available capacity.

Intuitively, for any amount of capacity available to be filled by small items,
and a minimum increase in profit, the optimal solution either packs a single
item from $\mathcal{I}_{S}(t)\setminus\widetilde{\mathcal{I}}_{S}(t)$ in which
case the loss by ignoring items in this set is bounded by the maximum reward
of any small item, or the optimal solution only contains items from
$\widetilde{\mathcal{I}}_{S}(t)$ in which case the space used by this optimal
set of items is lower bounded by the a fractional packing of the highest
density items in $\widetilde{I}_{S}(t)$. During Algorithm 3, one of the
solutions we would consider would be the integral items of this fractional
solution, and lose at most $\frac{1}{2T}\epsilon P_{0}$ in profit, and obtain
a solution with still smaller space used (more leftover capacity) than the
fractional solution. Accumulation of these errors for $t$ periods then will
give us the invariant: the partial solution $\widetilde{A}_{t}(p)$ obtained as
above has more leftover capacity than any solution obtained by selecting items
from $\cup_{t^{\prime}=1}^{t}\mathcal{I}_{L}(t^{\prime})$ with rounded rewards
and rounded penalties, and items from
$\cup_{t^{\prime}=1}^{t}\mathcal{I}_{S}(t^{\prime})$ with original (unrounded)
rewards such that the rounded total profit is at least $p+\frac{1}{2T}\epsilon
P_{0}t+\kappa t$.

Our main theorem for the approximation ratio for MPBKP follows.

######  Theorem 4 (Partially restating Theorem 2).

Algorithm 5 is a fully polynomial approximation scheme for the MPBKP-S, which
achieves $(1+\epsilon)$ approximation ratio with running time
$\mathcal{O}\left(\frac{Tn\log n}{\epsilon^{2}}\right)$.

##  5 A greedy algorithm for a special case of MPBKP-SS

In this subsection, we consider the special case of MPBKP-SS when all items
have the same size, i.e., $q_{i}=q,\forall i\in[n]$. We again only present for
the case $B_{t}=B,\forall t\in[T]$. We note that in the deterministic problems
(MPBKP or MPBKP-S), when items all have the same size, greedily adding items
one by one in decreasing order of their rewards leads to the optimal solution.
For MPBKP-SS, as the capacities are now stochastic, we wonder if there is any
greedy algorithm performs well. We propose Algorithm 6, where we start with an
empty set, and greedily insert the item that brings the maximum increment on
expected profit, and we stop if adding any of the remaining items does not
increase the expected profit.

Algorithm 6 Greedy algorithm according to profit change

1:${\mathcal{S}}\leftarrow\emptyset$

2:$s\leftarrow 1$

3:while $s==1$ do

4:
$i^{*}\leftarrow\operatorname*{arg\,max}_{i\notin{\mathcal{S}}}\left\\{\mathcal{P}({\mathcal{S}}\cup\\{i\\})-\mathcal{P}({\mathcal{S}})\right\\}$

5: if
$\mathcal{P}({\mathcal{S}}\cup\\{i^{*}\\})-\mathcal{P}({\mathcal{S}})\geq 0$
then

6: ${\mathcal{S}}\leftarrow{\mathcal{S}}\cup\\{i^{*}\\}$

7: else

8: $s\leftarrow 0$

9: end if

10:end while

11:${\mathcal{S}}_{p}\leftarrow{\mathcal{S}}$

12:Return ${\mathcal{S}}_{p}$

Let ${\mathcal{S}}^{*}$ be an optimal solution, i.e.,
${\mathcal{S}}^{*}\in\arg\max_{{\mathcal{S}}\subseteq[n]}\mathcal{P}({\mathcal{S}}):=\mathcal{R}({\mathcal{S}})-B\cdot\Phi({\mathcal{S}})$,
where

$\Phi({\mathcal{S}}):=\mathbb{E}\left\\{\sum_{t=1}^{T}\left[\sum_{j\in\mathcal{I}(t)\cap{\mathcal{S}}}q_{j}-\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{j\in{\mathcal{S}}:t^{\prime}+1\leq
d_{j}\leq t-1}q_{j}\right\\}\right]^{+}\right\\}$

is the expected quantity of overflow on set ${\mathcal{S}}$, and let
${\mathcal{S}}_{p}$ be the set output by Algorithm 6. Then, we have the
following theorem.

######  Theorem 5 (Restating Theorem 3).

Algorithm 6 achieves $2$-approximation factor for MPBKP-SS when items have the
same size, i.e.,
$\mathcal{P}({\mathcal{S}}_{p})\geq\frac{1}{2}\mathcal{P}({\mathcal{S}}^{*})$
in $\mathcal{O}\left(n^{2}T|\Omega|\right)$.

The proof of the $2$-approximation could be more nontrivial than one may
think. The idea is to look at the greedy solution set ${\mathcal{S}}_{p}$ and
the optimal solution set ${\mathcal{S}}^{*}$, where we will use the dual to
characterize the optimal solution on each sample path. By swapping each item
in ${\mathcal{S}}_{p}$ to ${\mathcal{S}}^{*}$ in replacement of the same item
or two other items, we construct a sequence of partial solutions of the greedy
algorithm as well as modified optimal solution set, while maintaining the
invariant that the profit of ${\mathcal{S}}^{*}$ is bounded by the sum of two
times the profit of items in ${\mathcal{S}}_{p}$ swapped into
${\mathcal{S}}^{*}$ so far and the additional profit of remaining items in the
modified optimal solution set. We leave the formal proof of Theorem 5 to
Appendix A.3.

##  6 Comments and Future Directions

The current work represents to the best of our knowledge the first FPTAS for
the two multi-period variants of the classical knapsack problem. For MPBKP, we
obtained the runtime
$\tilde{\mathcal{O}}\left(n+(T^{3.25}/\epsilon^{2.25})\right)$. This was done
via the function approximation approach, where a function is approximated for
each period. The runtime increases in $T$ since we conduct $T$ number of
rounding downs, one after each $(\max,+)$-convolution. An alternative
algorithm with runtime
$\tilde{\mathcal{O}}\left(n+\frac{T^{2}}{\epsilon^{3}}\right)$ is also
provided in Appendix B. Note that the function we approximated is in the same
form as used in the 0-1 knapsack problem (Chan, , 2018). It is thus
interesting to ask if we could instead directly approximate the following
function:

$f_{\mathcal{I}}(c)=\max_{x}\left\\{\sum_{i\in\mathcal{I}}r_{i}x_{i}\ :\
\sum_{i\in\cup_{t^{\prime}=1}^{t}\mathcal{I}(t^{\prime})}q_{i}x_{i}\leq
c_{t},\forall t\in[T],\ x\in\\{0,1\\}^{n}\right\\},$

where $\mathcal{I}=\cup_{t=1}^{T}\mathcal{I}(t)$ and
$c=\\{c_{1},\ldots,c_{T}\\}$ is a $T$-dimensional vector. Here we impose all
$T$ constraints in the function. The hope is that, if the above function could
be approximated, and if we could properly define the $(\max,+)$-convolution on
$T$ dimensional vectors (and have a fairly easy computation of it), then we
may get an algorithm that depends more mildly on $T$.

For MPBKP-S and MPBKP-SS, there seems to be less we can do without further
assumptions. One direction to explore is parameterized approximation schemes:
assuming that in the optimal solution, the total (expected) penalty is at most
$\beta$ fraction of the total reward. Then we may just focus on rewards. Our
ongoing work suggests that an approximation factor of
$\left(1+\frac{\epsilon}{1-\beta}\right)$ may be achieved in
$\tilde{\mathcal{O}}\left(n+(T^{3.25}/\epsilon^{2.25})\right)$ for MPBKP-S,
and the same approximation factor in
$\tilde{\mathcal{O}}\left(n+\frac{1}{\epsilon^{T}}\right)$ for MPBKP-SS.

We further note that the objective function for the three multiperiod variants
are in fact submodular (but not non-negative, or monotone). Whether we can get
a constant competitive solution in time $\widetilde{\mathcal{O}}(n)$, using
approaches in submodular function maximization, is also an intriguing open
problem.

Finally, motivated by applications, one natural extension that the authors are
working on now is when there is a general non-decreasing cost function
$\phi_{t}(\Delta c)$ for procuring capacity $\Delta c$ at time $t$, and the
goal is to admit a profit maximizing set of items when the unused capacity can
be carried forward. Another extension is when there is a bound on the leftover
capacity that can be carried forward.

## References

  * Andonov et al., (2000) Andonov, R., Poirriez, V., and Rajopadhye, S. (2000).  Unbounded knapsack problem: Dynamic programming revisited.  European Journal of Operational Research, 123(2):394–407.
  * Aouad and Segev, (2020) Aouad, A. and Segev, D. (2020).  An approximate dynamic programming approach to the incremental knapsack problem.  arXiv preprint arXiv:2010.07633.
  * Bienstock et al., (2013) Bienstock, D., Sethuraman, J., and Ye, C. (2013).  Approximation algorithms for the incremental knapsack problem via disjunctive programming.  arXiv preprint arXiv:1311.4563.
  * Chan, (2018) Chan, T. M. (2018).  Approximation Schemes for 0-1 Knapsack.  In Seidel, R., editor, 1st Symposium on Simplicity in Algorithms (SOSA 2018), volume 61 of OpenAccess Series in Informatics (OASIcs), pages 5:1–5:12, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Chekuri and Khanna, (2005) Chekuri, C. and Khanna, S. (2005).  A polynomial time approximation scheme for the multiple knapsack problem.  SIAM Journal on Computing, 35(3):713–728.
  * Della Croce et al., (2019) Della Croce, F., Pferschy, U., and Scatamacchia, R. (2019).  On approximating the incremental knapsack problem.  Discrete Applied Mathematics.
  * Faaland, (1981) Faaland, B. H. (1981).  The multiperiod knapsack problem.  Operations Research, 29(3):612–616.
  * Faenza and Malinovic, (2018) Faenza, Y. and Malinovic, I. (2018).  A ptas for the time-invariant incremental knapsack problem.  In International Symposium on Combinatorial Optimization, pages 157–169. Springer.
  * Faenza et al., (2020) Faenza, Y., Segev, D., and Zhang, L. (2020).  Approximation algorithms for the generalized incremental knapsack problem.  arXiv preprint arXiv:2009.07248.
  * Hartline and Sharp, (2006) Hartline, J. and Sharp, A. (2006).  An incremental model for combinatorial maximization problems.  In Àlvarez, C. and Serna, M., editors, Experimental Algorithms, pages 36–48, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Ibarra and Kim, (1975) Ibarra, O. H. and Kim, C. E. (1975).  Fast approximation algorithms for the knapsack and sum of subset problems.  Journal of the ACM (JACM), 22(4):463–468.
  * Jansen, (2012) Jansen, K. (2012).  A fast approximation scheme for the multiple knapsack problem.  In Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., and Turán, G., editors, SOFSEM 2012: Theory and Practice of Computer Science, pages 313–324, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Jin, (2019) Jin, C. (2019).  An Improved FPTAS for 0-1 Knapsack.  In Baier, C., Chatzigiannakis, I., Flocchini, P., and Leonardi, S., editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 76:1–76:14, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * Kellerer and Pferschy, (2004) Kellerer, H. and Pferschy, U. (2004).  Improved dynamic programming in connection with an fptas for the knapsack problem.  Journal of Combinatorial Optimization, 8(1):5–11.
  * Kellerer et al., (2004) Kellerer, H., Pferschy, U., and Pisinger, D. (2004).  Knapsack Problems.  Springer.
  * Lau and Lim, (2004) Lau, H. C. and Lim, M. K. (2004).  Multi-period multi-dimensional knapsack problem and its application to available-to-promise.
  * Lawler, (1979) Lawler, E. L. (1979).  Fast approximation algorithms for knapsack problems.  Mathematics of Operations Research, 4(4):339–356.
  * Lin and Chen, (2010) Lin, E. Y. and Chen, M. (2010).  A dynamic programming approach to the multiple-choice multi-period knapsack problem and the recursive apl2 code.  Journal of Information and Optimization Sciences, 31(2):289–303.
  * Lin and Wu, (2004) Lin, E. Y. and Wu, C.-M. (2004).  The multiple-choice multi-period knapsack problem.  Journal of the Operational Research Society, 55(2):187–197.
  * Mathews, (1896) Mathews, G. B. (1896).  On the partition of numbers.  Proceedings of the London Mathematical Society, 1(1):486–490.
  * Moreno et al., (2010) Moreno, E., Espinoza, D., and Goycoolea, M. (2010).  Large-scale multi-period precedence constrained knapsack problem: a mining application.  Electronic notes in discrete mathematics, 36:407–414.
  * Randeniya, (1994) Randeniya, R. (1994).  Multiple-choice Multi-period Knapsack Problem (MCMKP): Applicationand Solution Approach.  University of New Brunswick, Faculty of Administration.
  * Rhee, (2015) Rhee, D. (2015).  Faster fully polynomial approximation schemes for knapsack problems.  PhD thesis, Massachusetts Institute of Technology.
  * Samavati et al., (2017) Samavati, M., Essam, D., Nehring, M., and Sarker, R. (2017).  A methodology for the large-scale multi-period precedence-constrained knapsack problem: an application in the mining industry.  International Journal of Production Economics, 193:12–20.
  * Vazirani, (2013) Vazirani, V. V. (2013).  Approximation algorithms.  Springer Science & Business Media.

##  Appendix A Omitted Proofs

###  A.1 Proofs for Section 3

###### Proof of Proposition 1.

We show that the solution corresponding to $f_{T}(c)$ is optimal for $c_{T}=c$
among all solutions feasible to (1). We prove by induction on $T$. Base case
is $T=1$, this reduces to 0-1 Knapsack problem, and by definition, the
solution corresponding to $f_{\mathcal{I}(1)}(c)$ is the optimal feasible
solution when the Knapsack capacity is $c$. For the induction step, assume
that the solution of $f_{T-1}(c^{\prime})$ is the optimal feasible solution to
(1) for the $T-1$ period problem and $c_{T-1}=c^{\prime}$, we show that the
solution corresponding to $f_{T}(c)$ is also the optimal feasible solution to
(1) for the $T$ period problem and $c_{T}=c$.

By definition,

$f_{T}(c)=\left(\left(f_{T-1}\oplus
f_{\mathcal{I}(T)}\right)(c)\right)^{c_{T}}=\left(\max_{c^{\prime}\in\mathbb{R}}\left(f_{T-1}(c^{\prime})+f_{\mathcal{I}(T)}(c-c^{\prime})\right)\right)^{c}.$

We first show that $f_{T}(c)$ is at least the optimal value of (1) when
$c_{T}=c$. Suppose that, in the optimal solution of (1), the total size of
accepted items up to time $T-1$ is $\hat{c}$ with $\hat{c}<c$, then the
optimal value is $f_{T-1}(\hat{c})+f_{\mathcal{I}(T)}(c-\hat{c})$ since
$f_{T-1}(\hat{c})$ is the maximum achievable reward with $c_{T-1}=\hat{c}$ (by
induction assumption) and $f_{\mathcal{I}(T)}(c-\hat{c})$ is the maximum
achievable reward using items from $\mathcal{I}(T)$ with space constraint
$c-\hat{c}$. Thus, we have that the optimal value
$f_{T-1}(\hat{c})+f_{\mathcal{I}(T)}(c-\hat{c})\leq\left(\max_{c^{\prime}\in\mathbb{R}}\left(f_{T-1}(c^{\prime})+f_{\mathcal{I}(T)}(c-c^{\prime})\right)\right)^{c}=f_{T}(c)$.

We next show the other direction: the optimal value of (1) for the $T$ period
problem with $c_{T}=c$ is at least $f_{T}(c)$. It suffices to show that every
possible solution considered in $f_{T}(c)$ satisfies the feasibility
constraints in (1). By induction assumption, every solution of
$f_{T-1}(c^{\prime})$ satisfies the constraints up to time $T-1$. When
computing $f_{T}(c)$, we note that since $f_{T-1}(c^{\prime})$ is a function
truncated at $c_{T-1}$, which implies that $f_{T-1}(c^{\prime})=-\infty$ for
any $c^{\prime}>c_{T-1}$. Therefore, any $c^{\prime}>c_{T-1}$ must not be in
the solution of
$\max_{c^{\prime}\in\mathbb{R}}\left(f_{T-1}(c^{\prime})+f_{\mathcal{I}(T)}(c-c^{\prime})\right)$.
As a result, every solution of $f_{T}(c)$ is enforcing that ${c^{\prime}}\leq
c_{T-1}$, and satisfies the feasibility constraints up to time $T$.

Combining both directions, we conclude the induction step, and thus the proof
of the proposition. ∎

###### Proof of Lemma 2.

By the construction of $\tilde{f}_{t}$, it should be clear that
$\tilde{f}_{t}\leq f_{t}$. We prove that $(1+\epsilon)^{t}\tilde{f}_{t}\geq
f_{t}$ by induction on $t$. Base case is when $t=1$, we have that
$(1+\epsilon)\tilde{f}_{1}=(1+\epsilon)\tilde{f}_{\mathcal{I}(1)}^{c_{1}}\geq
f_{\mathcal{I}(1)}^{c_{1}}=f_{1}$, where the inequality follows from Lemma 1.
As for the induction step, assume that $(1+\epsilon)^{t-1}\tilde{f}_{t-1}\geq
f_{t-1}$, we show that $(1+\epsilon)^{t}\tilde{f}_{t}\geq f_{t}$. Again, by
Lemma 1 we have that

$(1+\epsilon)^{t-1}\tilde{f}_{\mathcal{I}(t)}\geq(1+\epsilon)\tilde{f}_{\mathcal{I}(t)}\geq
f_{\mathcal{I}(t)}.$

Combined with the induction hypothesis, we have that

$(1+\epsilon)^{t-1}\left(\tilde{f}_{t-1}\oplus\tilde{f}_{\mathcal{I}(t)}\right)=\left((1+\epsilon)^{t-1}\tilde{f}_{t-1}\right)\oplus\left((1+\epsilon)^{t-1}\tilde{f}_{\mathcal{I}(t)}\right)\geq
f_{t-1}\oplus f_{\mathcal{I}(t)}.$

Taking truncation on both sides, we have that

$(1+\epsilon)^{t-1}\hat{f}_{t}=(1+\epsilon)^{t-1}\left(\tilde{f}_{t-1}\oplus\tilde{f}_{\mathcal{I}(t)}\right)^{c_{t}}\geq\left(f_{t-1}\oplus
f_{\mathcal{I}(t)}\right)^{c_{t}}=f_{t}.$

Because of rounding down, we have that
$(1+\epsilon)\tilde{f}_{t}\geq\hat{f}_{t}$. Therefore,

$(1+\epsilon)^{t}\tilde{f}_{t}\geq(1+\epsilon)^{t-1}\hat{f}_{t}\geq f_{t}.$

This concludes the induction step, and thus the proof of the lemma. ∎

###  A.2 Proofs for Section 4

This section is devoted to the proof of Theorem 4. To proceed, we first
present the following result on Algorithm 2.

######  Lemma 3.

Given a set of partial solutions with leftover capacities $\widetilde{A}({p})$
for all
${p}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$,
the additional capacity available for packing $\Delta c$, and the set of large
items to be added $\mathcal{I}_{L}:=\\{1,\ldots,I_{L}\\}$, the output of
Algorithm 2, $\hat{A}(I_{L},p)$, satisfies:

$\displaystyle\hat{A}(I_{L},p)=\max_{\left\\{\begin{subarray}{c}\mathcal{I}^{\prime},\bar{p}\
:\ \mathcal{I}^{\prime}\subseteq\mathcal{I}_{L}\\\
\Delta\hat{\mathcal{P}}(\mathcal{I}^{\prime},\widetilde{A}(\bar{p})+\Delta
c)\geq p-\bar{p}\\\
\bar{p}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa\end{subarray}\right\\}}\widetilde{A}(\bar{p})+\Delta
c-\mathcal{Q}(\mathcal{I}^{\prime}),\quad\forall p.$ (12)

That is, $\hat{A}(I_{L},p)$ is the maximum leftover capacity for any solution
with (rounded) profit at least $p$ obtained by adding items in
$\mathcal{I}_{L}$ to the solutions corresponding to $\widetilde{A}(\cdot)$.

###### Proof of Lemma 3.

We will prove a more general result than (12), i.e.,

$\displaystyle\hat{A}(i,p)=\max_{\left\\{\begin{subarray}{c}\mathcal{I}^{\prime},\bar{p}\
:\ \mathcal{I}^{\prime}\subseteq\\{1,\ldots,i\\}\\\
\Delta\hat{\mathcal{P}}(\mathcal{I}^{\prime},\widetilde{A}(\bar{p})+\Delta
c)\geq p-\bar{p}\\\
\bar{p}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa\end{subarray}\right\\}}\widetilde{A}(\bar{p})+\Delta
c-\mathcal{Q}(\mathcal{I}^{\prime}),\quad\forall p$ (13)

We prove this by induction. The base case ($i=0$) is vacuously true. Now we
assume that (13) holds for all $p\in\left\\{0,1,\ldots,\lceil
16T/\epsilon^{2}\rceil\right\\}\kappa$ and for all $k\in[i-1]$. Consider some
$p\in\left\\{0,1,\ldots,\lceil 16T/\epsilon^{2}\rceil\right\\}\kappa$, and let
$\mathcal{I}^{*}$ be any set achieving the maximum in (13) so that
$\hat{P}(\mathcal{I}^{*})\geq p-\bar{p}$ for some
$\bar{p}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$.
We will show that $\hat{A}(i,p)$ is at least the leftover capacity under
solution $\mathcal{I}^{*}$ via case analysis:

  * •

Case $i\notin\mathcal{I}^{*}$: In this case, the leftover capacity under
$\mathcal{I}^{*}$ is the leftover capacity by $d_{i}$, which is the sum of
leftover capacity in $\mathcal{I}^{*}$ by $d_{i-1}$ and
$c_{d_{i}}-c_{d_{i-1}}$. By induction hypothesis, $\hat{A}(i-1,p)$ is no less
than the leftover capacity of $\mathcal{I}^{*}$ by $d_{i-1}$, and therefore,
by lines $4$ and $8$, $\hat{A}(i,p)\geq\hat{A}(i-1,p)+c_{d_{i}}-c_{d_{i-1}}$
which in turn is no less than the leftover capacity under $\mathcal{I}^{*}$ by
$d_{i}$. By optimality of $\mathcal{I}^{*}$, all the inequalities must be
equalities.

  * •

Case $i\in\mathcal{I}^{*}$: Let
$\mathcal{I}^{\prime}=\mathcal{I}^{*}\setminus\\{i\\}$, and let
$p^{\prime}=\hat{\mathcal{P}}(\mathcal{I}^{\prime})$ be its rounded profit.
Then by induction hypothesis, $\hat{A}(i-1,p^{\prime})$ is no less than the
leftover capacity under $\mathcal{I}^{\prime}$ by $d_{i-1}$. Further, by
packing item $i$ in the solution corresponding to $\hat{A}(i-1,p^{\prime})$,
the change in profit is larger than by packing item $i$ in
$\mathcal{I}^{\prime}$ (the penalty is no less under $\mathcal{I}^{\prime}$
since it has weakly smaller leftover capacity). Therefore, packing item $i$ in
the solution corresponding to $\hat{A}(i-1,p^{\prime})$ gives a solution with
at least as large a rounded profit as $p$ and at least as much leftover
capacity by $d_{i}$ as $\mathcal{I}^{*}$. Therefore, in turn $\hat{A}(i,p)$ is
at least as much as the leftover capacity in $\mathcal{I}^{*}$. Since we
assume $\mathcal{I}^{*}$ to have the largest leftover capacity with profit at
least $p$, all the inequalities must be equalities.

This completes the induction step, and thus the proof of the lemma. ∎

Next, we have the following Lemma as a preparation for our result on
$\widetilde{A}(p)$ of Algorithm 3.

######  Lemma 4.

Given some capacity $c$ and a set of small items $\mathcal{I}_{S}$ with
$p_{max}:=\max_{i\in\mathcal{I}_{S}}p_{i}$, let ${\mathcal{S}}^{*}$ be the
profit-optimal subset, i.e.,
${\mathcal{S}}^{*}=\arg\max_{{\mathcal{S}}\subseteq\mathcal{I}_{S}}\mathcal{P}({\mathcal{S}})=\mathcal{R}({\mathcal{S}})-B\left(\mathcal{Q}({\mathcal{S}})-c\right)^{+}$.
Further, let $\widetilde{\mathcal{I}}_{S}:=\\{i\in\mathcal{I}_{S}\mid
q_{i}\leq c\\}$ and relabel the items in $\widetilde{\mathcal{I}}_{S}$ as
$\left\\{1^{\prime},\ldots,|\widetilde{\mathcal{I}}_{S}|^{\prime}\right\\}$
(in decreasing order of reward density $r_{i}/q_{i}$). Let $i^{\prime}$ be
such that $\sum_{j^{\prime}=1^{\prime}}^{i^{\prime}}q_{j^{\prime}}\leq c$ and
$\sum_{j^{\prime}=1^{\prime}}^{(i+1)^{\prime}}q_{j^{\prime}}>c$. Then, the
solution ${\mathcal{S}}^{\prime}:=\\{1^{\prime},\ldots,i^{\prime}\\}$
satisfies

  * •

$\mathcal{Q}({\mathcal{S}}^{\prime})\leq\mathcal{Q}({\mathcal{S}}^{*})$,

  * •

$\mathcal{P}({\mathcal{S}}^{\prime})\geq\mathcal{P}({\mathcal{S}}^{*})-p_{max}$.

###### Proof of Lemma 4.

The first item can be shown by contradiction. Suppose that to the contrary
$\mathcal{Q}({\mathcal{S}}^{\prime})>\mathcal{Q}({\mathcal{S}}^{*})$, that is,
${\mathcal{S}}^{\prime}$ uses more space than ${\mathcal{S}}^{*}$. Since the
items in ${\mathcal{S}}^{\prime}$ have the highest reward densities, it is in
fact the optimal solution which uses space
$\mathcal{Q}({\mathcal{S}}^{\prime})<c$. Since the optimal profit is non-
decreasing in the capacity $c$, this violates optimality of
${\mathcal{S}}^{*}$.

To see the second item, we look at two different cases. First, if
${\mathcal{S}}^{*}\cap\left(\mathcal{I}_{S}\setminus\widetilde{\mathcal{I}_{S}}\right)\neq\emptyset$,
i.e., the optimal packing ${\mathcal{S}}^{*}$ includes some item $i^{*}$ with
$q_{i^{*}}>c$, then, there should be only one item in ${\mathcal{S}}^{*}$,
i.e., ${\mathcal{S}}^{*}=\\{i^{*}\\}$. In this case,
$\mathcal{P}({\mathcal{S}}^{*})=p_{i^{*}}=p_{max}$ and thus
$\mathcal{P}({\mathcal{S}}^{\prime})\geq\mathcal{P}(\emptyset)=0=\mathcal{P}({\mathcal{S}}^{*})-p_{max}$.

Second, if
${\mathcal{S}}^{*}\cap\left(\mathcal{I}_{S}\setminus\widetilde{\mathcal{I}_{S}}\right)=\emptyset$,
then
${\mathcal{S}}^{*}=\arg\max_{{\mathcal{S}}\subseteq\widetilde{I}_{S}}\mathcal{P}({\mathcal{S}})$.
Note that $\mathcal{P}({\mathcal{S}}^{*})$ is upper bounded by the reward for
the fractional packing:
$\mathcal{P}({\mathcal{S}}^{*})\leq\mathcal{R}_{LP}:=\mathcal{R}({\mathcal{S}}^{\prime})+r_{(i+1)^{\prime}}\cdot\frac{c-\mathcal{Q}({\mathcal{S}}^{\prime})}{q_{(i+1)^{\prime}}}\leq\mathcal{R}({\mathcal{S}}^{\prime})+r_{(i+1)^{\prime}}=\mathcal{P}({\mathcal{S}}^{\prime})+p_{(i+1)^{\prime}}\leq\mathcal{P}({\mathcal{S}}^{\prime})+p_{max}$.

In either cases, we conclude that
$\mathcal{P}({\mathcal{S}}^{\prime})\geq\mathcal{P}({\mathcal{S}}^{*})-p_{max}$.
∎

Before presenting our result on $\widetilde{A}_{t}(p)$, we will need the
following definitions. For a solution
${\mathcal{S}}={\mathcal{S}}(1)\cup{\mathcal{S}}(2)\cup\cdots\cup{\mathcal{S}}(T)$
with ${\mathcal{S}}(t)={\mathcal{S}}_{L}(t)\cup{\mathcal{S}}_{S}(t)$, denoting
the items with deadline $t$ in ${\mathcal{S}}$, let the large items be indexed
as ${\mathcal{S}}_{L}(t)=(i^{(t)}_{1},\ldots,i^{(t)}_{L_{t}})$ in the order in
which Algorithm 2 considers them, and the small items be indexed arbitrarily
${\mathcal{S}}_{S}(t)=\left(j^{(t)}_{1},\ldots,j^{(t)}_{S_{t}}\right)$. Let
${\mathcal{S}}_{L}:={\mathcal{S}}_{L}(1)\cup\cdots\cup{\mathcal{S}}_{L}(T)$
and
${\mathcal{S}}_{S}:={\mathcal{S}}_{S}(1)\cup\cdots\cup{\mathcal{S}}_{S}(T)$
denote the large and small items in ${\mathcal{S}}$, respectively (this
depends on the choice of $P_{0}$ but we suppress the dependence for brevity).
We define the rounded profit of ${\mathcal{S}}$ as:

$\displaystyle\tilde{\mathcal{P}}({\mathcal{S}})$
$\displaystyle=\hat{\mathcal{R}}({\mathcal{S}}_{L})-\sum_{t=1}^{T}\sum_{k=1}^{L_{t}}\left\lceil
B\left(\sum_{\ell\leq k}q_{i^{(t)}_{\ell}}-\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau<t}\mathcal{Q}({\mathcal{S}}(\tau))\right\\}\right)^{+}\right\rceil_{\kappa}$
$\displaystyle\quad+\sum_{t=1}^{T}\left\lfloor\mathcal{R}({\mathcal{S}}_{S}(t))-B\left(\mathcal{Q}({\mathcal{S}}(t))-\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau<t}\mathcal{Q}({\mathcal{S}}(\tau))\right\\}\right)^{+}\right\rfloor_{\kappa}.$
(14)

That is, we add the rounded rewards of the large items, and for small items,
we first group the small items by their deadlines, and for each deadline we
round the sum of unrounded rewards of small item. Further, let

$\widetilde{C}_{t}(p):=\max_{\left\\{\begin{subarray}{c}{\mathcal{S}}\subseteq\bigcup_{t^{\prime}=1}^{t}\mathcal{I}(t^{\prime})\
:\ \tilde{\mathcal{P}}({\mathcal{S}})\geq p\end{subarray}\right\\}}\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau\leq
t}\mathcal{Q}({\mathcal{S}}(\tau))\right\\}$

denote the feasible partial solution with largest leftover capacity at time
$t$ and rounded total profit at least $p$. Then, we have the following lemma.

######  Lemma 5.

For any $t=1,\ldots,T$ and any
$p^{\prime}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$,
we have that $\widetilde{A}_{t}(p)\geq\widetilde{C}_{t}(p^{\prime})$ for some
$p\geq p^{\prime}-\frac{1}{2T}\epsilon P_{0}t-\kappa t\geq
r^{\prime}-\frac{1}{2T}\epsilon(1-\epsilon/4)P_{0}t$. That is, for any rounded
total profit $p^{\prime}$ by time $t$, there exists some partial solution
$\widetilde{A}_{t}$ of Algorithm 4 which has at least as much leftover
capacity at time $t$ the optimal solution $\widetilde{C}_{t}(p^{\prime})$, and
has rounded profit $p$ not too much smaller than $p^{\prime}$.

###### Proof of Lemma 5.

We prove by induction on $t$. Base case is when $t=1$. Let
${\mathcal{S}}^{\prime}$ be the solution corresponding to
$\widetilde{C}_{1}(p^{\prime})$, i.e.,
${\mathcal{S}}^{\prime}:=\arg\max_{\left\\{\begin{subarray}{c}{\mathcal{S}}\subseteq\mathcal{I}(1)\\\
\tilde{\mathcal{P}}({\mathcal{S}})\geq
p^{\prime}\end{subarray}\right\\}}c_{1}-\mathcal{Q}({\mathcal{S}})$, and let
${\mathcal{S}}^{\prime}_{L}={\mathcal{S}}^{\prime}\cap\mathcal{I}_{L}$,
${\mathcal{S}}^{\prime}_{S}={\mathcal{S}}^{\prime}\cap\mathcal{I}_{S}$. Then
$\tilde{\mathcal{P}}({\mathcal{S}}^{\prime}_{L})=\hat{\mathcal{P}}({\mathcal{S}}_{L}^{\prime})$.
By Lemma 3,
$\hat{A}(I_{L}(1),\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime}))$ is the
maximum leftover capacity using items in $\mathcal{I}_{L}(1)$ earning rounded
profit $\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime})$. Thus,
$\hat{A}_{1}(\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime}))=\hat{A}(I_{L}(1),\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime}))\geq
c_{1}-\mathcal{Q}({\mathcal{S}}_{L}^{\prime})$. Let
${\mathcal{S}}^{\prime\prime}_{L}$ be the solution corresponding to
$\hat{A}_{1}(\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime}))$, and thus
$\mathcal{Q}({\mathcal{S}}_{L}^{\prime\prime})\leq\mathcal{Q}({\mathcal{S}}_{L}^{\prime})$.
Consider appending the partial solution ${\mathcal{S}}_{L}^{\prime\prime}$
using items from $\mathcal{I}_{S}(1)$. Let ${\mathcal{S}}_{S}^{\prime\prime}$
be the small item set obtained by adding small items greedily in their reward
densities, subject to the constraint that
$\mathcal{Q}({\mathcal{S}}_{S}^{\prime\prime})\leq\mathcal{Q}({\mathcal{S}}_{S}^{\prime})$.
Then, by Lemma 4, with ${\mathcal{S}}_{S}^{\prime\prime}$ being the greedy
solution, $\mathcal{Q}({\mathcal{S}}_{S}^{\prime})$ being the capacity
constraint and ${\mathcal{S}}_{S}^{\prime}$ being the optimal filling of small
items in $\mathcal{I}_{S}(1)$, we conclude that

${\mathcal{P}}({{\mathcal{S}}}_{S}^{\prime\prime})\geq{\mathcal{P}}({\mathcal{S}}_{S}^{\prime})-\frac{1}{2T}\epsilon
P_{0}.$

Therefore,
$p^{\prime}=\tilde{\mathcal{P}}({\mathcal{S}}^{\prime})=\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime}\cup{\mathcal{S}}_{S}^{\prime})$
=
$\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime})+\Delta\tilde{\mathcal{P}}({\mathcal{S}}_{S}^{\prime},c_{1}-\mathcal{Q}({\mathcal{S}}_{L}^{\prime}))\leq\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime\prime})+\Delta\tilde{\mathcal{P}}({{\mathcal{S}}}_{S}^{\prime\prime},c_{1}-\mathcal{Q}({\mathcal{S}}_{L}^{\prime}))+\frac{1}{2T}\epsilon
P_{0}+\kappa\leq\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime\prime})+\Delta\tilde{\mathcal{P}}({{\mathcal{S}}}_{S}^{\prime\prime},c_{1}-\mathcal{Q}({\mathcal{S}}_{L}^{\prime\prime}))+\frac{1}{2T}\epsilon
P_{0}+\kappa=\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime\prime}\cup{{\mathcal{S}}}_{S}^{\prime\prime})+\frac{1}{2T}\epsilon
P_{0}+\kappa$. Let
$p=\tilde{\mathcal{P}}({\mathcal{S}}_{L}^{\prime\prime}\cup{{\mathcal{S}}}_{S}^{\prime\prime})$.
From Algorithm 3, we know that since ${\mathcal{S}}_{S}^{\prime\prime}$
includes the small items in $\widetilde{\mathcal{I}}_{S}(1)$ with the highest
reward densities, the solution
${\mathcal{S}}_{L}^{\prime\prime}\cup{\mathcal{S}}_{S}^{\prime\prime}$ is one
feasible solution for $\widetilde{A}_{1}(p)$. We thus have that

$\widetilde{A}_{1}(p)\geq
c_{1}-\mathcal{Q}({\mathcal{S}}_{L}^{\prime\prime}\cup{\mathcal{S}}_{S}^{\prime\prime})\geq
c_{1}-\mathcal{Q}({\mathcal{S}}^{\prime})=\widetilde{C}_{1}(p^{\prime}),$

where $p\geq p^{\prime}-\frac{1}{2T}\epsilon R_{0}-\kappa$, and the second
inequality follows from the facts that
$\mathcal{Q}({\mathcal{S}}_{L}^{\prime\prime})\leq\mathcal{Q}({\mathcal{S}}_{L}^{\prime})$
and
$\mathcal{Q}({\mathcal{S}}_{S}^{\prime\prime})\leq\mathcal{Q}({\mathcal{S}}_{S}^{\prime})$.

For the induction step, assume that for all
$p^{\prime\prime}\in\left\\{0,1,\ldots,\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\right\\}\cdot\kappa$,
we have that $\widetilde{A}_{t-1}(p)\geq\widetilde{C}_{t-1}(p^{\prime\prime})$
for some $p\geq p^{\prime\prime}-\frac{1}{2T}\epsilon P_{0}(t-1)-\kappa(t-1)$.
We want to show that for all $p^{\prime}$,
$\widetilde{A}_{t}(p)\geq\widetilde{C}_{t}(p^{\prime})$ for some $p\geq
p^{\prime}-\frac{1}{2T}\epsilon P_{0}t-\kappa t$. Let ${\mathcal{S}}^{\prime}$
be the solution corresponding to $\widetilde{C}_{t}(p^{\prime})$, i.e.,

${\mathcal{S}}^{\prime}:=\arg\max_{\left\\{\begin{subarray}{c}{\mathcal{S}}\subseteq\bigcup_{t^{\prime}=1}^{t}\mathcal{I}(t^{\prime})\
:\ \tilde{\mathcal{P}}({\mathcal{S}})\geq
p^{\prime}\end{subarray}\right\\}}\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau\leq
t}\mathcal{Q}({\mathcal{S}}(\tau))\right\\},$

and let
${\mathcal{S}}_{L}^{\prime}={\mathcal{S}}^{\prime}\cap\mathcal{I}_{L}$,
${\mathcal{S}}^{\prime}_{S}={\mathcal{S}}^{\prime}\cap\mathcal{I}_{S}$. Let
${\mathcal{S}}^{\prime}(t):=\\{i\in{\mathcal{S}}^{\prime}\mid d_{i}=t\\}$ and
consider the partial solution
$\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})$. By induction
assumption, there exists some partial solution
$\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})$ such that
$\mathcal{Q}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\right)\leq\mathcal{Q}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\right)$,
and that
$\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\right)\geq\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\right)-\frac{1}{2T}\epsilon
P_{0}(t-1)-\kappa(t-1)$.

First, we fill the partial solution
$\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})$ using
items from $\mathcal{I}_{L}(t)$ according to Algorithm 2. Note that one
feasible solution is ${\mathcal{S}}_{L}^{\prime}(t)$ which results in
$\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)$.
This keeps
$\mathcal{Q}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)\leq\mathcal{Q}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)$
while having
$\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)\geq\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)-\frac{1}{2T}\epsilon
P_{0}(t-1)-\kappa(t-1)$. Suppose that after filling items from
$\mathcal{I}_{L}(t)$ using DP in Algorithm 2, the resulting set corresponding
to
$\hat{A}_{t}\left(\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)\right)$
is $\widetilde{{\mathcal{S}}}$, then this $\widetilde{{\mathcal{S}}}$ would
only use less space and earn more profit, i.e.,

$\displaystyle\mathcal{Q}\left(\widetilde{{\mathcal{S}}}\right)$
$\displaystyle\leq\mathcal{Q}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)\leq\mathcal{Q}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right),$
$\displaystyle\tilde{\mathcal{P}}\left(\widetilde{{\mathcal{S}}}\right)$
$\displaystyle\geq\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)$
$\displaystyle\geq\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\right)-\frac{1}{2T}\epsilon
P_{0}(t-1)-\kappa(t-1).$

Next, consider filling the partial solution $\widetilde{{\mathcal{S}}}$ using
items from $\mathcal{I}_{S}(t)$. Let ${\mathcal{S}}_{S}^{\prime\prime}(t)$ be
the small item set obtained by adding small items greedily in their reward
densities, subject to the constraint that
$\mathcal{Q}\left({\mathcal{S}}_{S}^{\prime\prime}(t)\right)\leq\mathcal{Q}\left({\mathcal{S}}_{S}^{\prime}(t)\right)$.
Then, by Lemma 4, with ${\mathcal{S}}_{S}^{\prime\prime}(t)$ being the greedy
solution, $\mathcal{Q}({\mathcal{S}}_{S}^{\prime}(t))$ being the capacity
constraint and ${\mathcal{S}}_{S}^{\prime}(t)$ being the optimal filling of
small items in $\mathcal{I}_{S}(t)$, we conclude that

${\mathcal{P}}({{\mathcal{S}}}_{S}^{\prime\prime}(t))\geq{\mathcal{P}}({\mathcal{S}}_{S}^{\prime}(t))-\frac{1}{2T}\epsilon
P_{0}.$

Therefore,

$\displaystyle p^{\prime}$
$\displaystyle=\tilde{\mathcal{P}}({\mathcal{S}}^{\prime})=\tilde{\mathcal{P}}\left(\cup_{t^{\prime}=1}^{t-1}{\mathcal{S}}^{\prime}(t^{\prime})\cup{\mathcal{S}}_{L}^{\prime}(t)\cup{\mathcal{S}}_{S}^{\prime}(t)\right)$
$\displaystyle\leq\tilde{\mathcal{P}}\left(\widetilde{{\mathcal{S}}}\cup{\mathcal{S}}_{S}^{\prime\prime}(t)\right)+\frac{1}{2T}\epsilon
P_{0}(t-1)+\kappa(t-1)+\frac{1}{2T}\epsilon P_{0}+\kappa$
$\displaystyle\leq\tilde{\mathcal{P}}\left(\widetilde{{\mathcal{S}}}\cup{{\mathcal{S}}}_{S}^{\prime\prime}(t)\right)+\frac{1}{2T}\epsilon
P_{0}t+\kappa t.$

Let
$p=\tilde{\mathcal{P}}\left(\widetilde{{\mathcal{S}}}\cup{{\mathcal{S}}}_{S}^{\prime\prime}(t)\right)$.
From Algorithm 3, we know that since ${\mathcal{S}}_{S}^{\prime\prime}(t)$
includes the small items in $\widetilde{\mathcal{I}}_{S}(t)$ with the highest
reward densities, the solution
$\widetilde{{\mathcal{S}}}\cup{\mathcal{S}}_{S}^{\prime\prime}(t)$ is one
feasible solution for $\widetilde{A}_{t}(p)$. We thus have that

$\displaystyle\widetilde{A}_{t}(p)$ $\displaystyle\geq\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau\leq
t}\mathcal{Q}\left(\left(\widetilde{{\mathcal{S}}}\cup{{\mathcal{S}}}_{S}^{\prime\prime}(t)\right)(\tau)\right)\right\\}$
$\displaystyle\geq\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau\leq
t}\mathcal{Q}({\mathcal{S}}^{\prime}(\tau))\right\\}=\widetilde{C}_{t}(p^{\prime}),$

where $p\geq p^{\prime}-\frac{1}{2T}\epsilon P_{0}t-\kappa t$. This finishes
the induction step, and thus the proof of the lemma. ∎

Using the above lemmas, we prove the following approximation result.

######  Proposition 3.

Let ${\mathcal{S}}^{\prime}$ denote the optimal solution set by Algorithm 4,
i.e., ${\mathcal{S}}^{\prime}$ is the solution set corresponding to
$\widetilde{A}_{T}(p^{*})$ where $p^{*}$ is the maximum $p$ such that
$\widetilde{A}_{T}(p)>-\infty$. Let ${\mathcal{S}}^{*}$ be the optimal
solution set to the original MPBKP-S. Then,

$\displaystyle\mathcal{P}({\mathcal{S}}^{\prime})\geq
p^{*}\geq(1-\epsilon-3\epsilon^{2}/8)\mathcal{P}({\mathcal{S}}^{*}).$

###### Proof.

Note that $\tilde{\mathcal{P}}({\mathcal{S}}^{\prime})=p^{*}$. Lemma 5 implies
that

$\widetilde{A}_{T}(p^{*})\geq\widetilde{C}_{T}\left(p^{*}+\frac{1}{2T}\epsilon
P_{0}T+\kappa T\right)=\widetilde{C}_{T}\left(p^{*}+\frac{1}{2}\epsilon
P_{0}+\kappa T\right).$

Since $\widetilde{C}_{T}(\tilde{\mathcal{P}}({\mathcal{S}}^{*}))>-\infty$, we
have that
$\widetilde{A}_{T}\left(\tilde{\mathcal{P}}({\mathcal{S}}^{*})-\frac{1}{2}\epsilon
P_{0}-\kappa
T\right)\geq\widetilde{C}_{T}(\tilde{\mathcal{P}}({\mathcal{S}}^{*}))>-\infty$.
Therefore,

$\mathcal{P}({\mathcal{S}}^{\prime})\geq
p^{*}\geq\tilde{\mathcal{P}}({\mathcal{S}}^{*})-\frac{1}{2}\epsilon
P_{0}-\kappa T.$

By the definition of $\tilde{\mathcal{P}}$ as in (A.2), for each large item,
the reward is rounded down by at most $\kappa$ and the penalty is rounded up
by at most $\kappa$, and all small items are together rounded down by at most
$\kappa T$. Note that each large items earns profit $p_{i}$ unless it is
paying more penalty than it would be by itself, which happens at most once at
each period. Thus, there are at most $\frac{2P_{0}}{\frac{1}{2T}\epsilon
P_{0}}+T=\frac{4T}{\epsilon}+T$ number of large items, and thus the total
number of rounding downs (for both large and small items) is bounded by
$\frac{4T}{\epsilon}+2T$. Therefore, we have that
$\mathcal{P}({\mathcal{S}}^{*})\leq\tilde{\mathcal{P}}({\mathcal{S}}^{*})+\left(\frac{4T}{\epsilon}+2T\right)\kappa$.
In conclusion,

$\displaystyle\mathcal{P}({\mathcal{S}}^{\prime})\geq p^{*}$
$\displaystyle\geq\tilde{\mathcal{P}}({\mathcal{S}}^{*})-\frac{1}{2}\epsilon
P_{0}-\kappa T$
$\displaystyle\geq\mathcal{P}({\mathcal{S}}^{*})-\left(\frac{4T}{\epsilon}+2T\right)\kappa-\frac{1}{2}\epsilon
P_{0}-T\kappa=\mathcal{P}({\mathcal{S}}^{*})-\epsilon P_{0}-3T\kappa$
$\displaystyle\geq\left(1-\epsilon-3\epsilon^{2}/8\right)\mathcal{P}({\mathcal{S}}^{*}).$

∎

It remains to validate Algorithm 5 in the search of $P_{0}$ which satisfies
(10). When Algorithm 5 terminates, it returns the last $p^{*}$ and the
solution set $\mathcal{S}^{\prime}$ corresponding to
$\widetilde{A}_{T}(p^{*})$. We then have the following lemmas.

######  Lemma 6.

Algorithm 5 terminates within $\log n$ iterations of the “while” loop (line
3).

###### Proof of Lemma 6.

When $P_{0}$ satisfies (10), by Proposition 3 we have that

$p^{*}\geq(1-\epsilon)\mathcal{P}({\mathcal{S}}^{*})\geq(1-\epsilon)P_{0}.$

Thus, the “while” loop terminates when $P_{0}$ satisfies (10), if not before
$P_{0}$ satisfies (10). When $P_{0}$ satisfies (10), we would also have
$\mathcal{P}({\mathcal{S}}^{*})/2\leq
P_{0}\leq\mathcal{P}({\mathcal{S}}^{*})$. Therefore, the number of iterations
is upper bounded by

$\text{number of
iterations}\leq\log\frac{\bar{P}/2}{\mathcal{P}({\mathcal{S}}^{*})/2}\leq\log
n,$

where we have used the fact that $\bar{P}\leq nP\leq
n\mathcal{P}({\mathcal{S}}^{*})$. ∎

######  Lemma 7.

After running Algorithm 5, suppose $\mathcal{S}^{\prime}$ is the solution set
corresponding to $\widetilde{A}_{T}(p^{*})$, and $\mathcal{S}^{*}$ is the
optimal solution set to the original MPBKP-S. Then,

$\mathcal{P}(\mathcal{S}^{\prime})\geq(1-\epsilon)\mathcal{P}(\mathcal{S}^{*}).$

###### Proof of Lemma 7.

If the “while” loop terminates when $P_{0}>\mathcal{P}({\mathcal{S}}^{*})$,
i.e., it stops before $P_{0}$ falls below $\mathcal{P}({\mathcal{S}}^{*})$,
then we have that

$\mathcal{P}({\mathcal{S}}^{\prime})\geq
p^{*}\geq(1-\epsilon)P_{0}>(1-\epsilon)\mathcal{P}({\mathcal{S}}^{*}).$

Otherwise, from the proof of Lemma 6 we know that the “while” loop must
terminate when $P_{0}$ first falls below $\mathcal{P}({\mathcal{S}}^{*})$,
which implies that the last $P_{0}$ satisfies (10). Then by Proposition 3 we
again have that

$\mathcal{P}({\mathcal{S}}^{\prime})\geq(1-\epsilon)\mathcal{P}({\mathcal{S}}^{*}).$

In either case, the solution we obtained from Algorithm 5 achieves
$(1-\epsilon)$ optimal. ∎

With the above Lemmas, we are in a position to prove Theorem 4.

###### Proof of Theorem 4.

By Lemma 7, the solution found is within $(1-\epsilon)$ factor of
$\mathcal{P}({\mathcal{S}}^{*})$. Since the running time of the algorithm is
$\mathcal{O}\left(n\cdot\left\lceil\frac{16T}{\epsilon^{2}}\right\rceil\cdot\log
n\right)=\mathcal{O}\left(\frac{Tn\log n}{\epsilon^{2}}\right)$, which is
polynomial in $n$ and $1/\epsilon$, the theorem follows. ∎

###  A.3 Proof of Theorem 5

This subsection is devoted to the proof of Theorem 5. The idea is to look at
the greedy solution set ${\mathcal{S}}_{p}$ and the optimal solution set
${\mathcal{S}}^{*}$, and by swapping each item in ${\mathcal{S}}_{p}$ to
${\mathcal{S}}^{*}$ in replacement of the same item or two other items, we
construct a sequence of partial solutions of the greedy algorithm as well as
modified optimal solution set, while maintaining the invariant that the profit
of ${\mathcal{S}}^{*}$ is bounded by the sum of two times the profit of items
in ${\mathcal{S}}_{p}$ swapped into ${\mathcal{S}}^{*}$ so far and the
additional profit of remaining items in the modified optimal solution set. We
will make this clear in the following.

To proceed, we first introduce some notations. Let
${\mathcal{S}}_{p}=\\{g_{1},\ldots,g_{l}\\}$ and
${\mathcal{S}}^{*}=\\{o_{1},\ldots,o_{m}\\}$, i.e., the items in greedy
solution is denoted by $g_{i}$’s and the items in the optimal solution is
denoted by $o_{i}$’s. Further, for any two sets of items ${\mathcal{S}}_{1}$
and ${\mathcal{S}}_{2}$, we define the incremental profit of adding
${\mathcal{S}}_{2}$ to the set ${\mathcal{S}}_{1}$ as

$\displaystyle\Delta\mathcal{P}({\mathcal{S}}_{1},{\mathcal{S}}_{2})=\mathcal{P}({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})-\mathcal{P}({\mathcal{S}}_{1}).$
(15)

Recall that $\Phi({\mathcal{S}})$ is the expected number of units of overflows
that penalties are paid, which will be referred as _overflow units_ in the
following. The incremental expected overflow units of adding
${\mathcal{S}}_{2}$ to the set ${\mathcal{S}}_{1}$ is defined as

$\displaystyle\Delta\Phi({\mathcal{S}}_{1},{\mathcal{S}}_{2})=\Phi({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})-\Phi({\mathcal{S}}_{1}).$
(16)

On a sample path of incremental capacities $\omega=\\{c_{t}\\}_{t=1}^{T}$, let
$a_{t}:=c_{t}-c_{t-1}$. Let $\mathcal{P}_{\omega}$ and $\Phi_{\omega}$ be the
profit and overflow units function, respectively, and the incremental profit
of adding ${\mathcal{S}}_{2}$ to the set ${\mathcal{S}}_{1}$ is

$\Delta\mathcal{P}_{\omega}({\mathcal{S}}_{1},{\mathcal{S}}_{2})=\mathcal{P}_{\omega}({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})-\mathcal{P}_{\omega}({\mathcal{S}}_{1}).$

Similarly, on sample path $\omega$, the incremental penalty of adding
${\mathcal{S}}_{2}$ to the set ${\mathcal{S}}_{1}$ is

$\Delta\Phi_{\omega}({\mathcal{S}}_{1},{\mathcal{S}}_{2})=\Phi_{\omega}({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})-\Phi_{\omega}({\mathcal{S}}_{1}).$

Then, the relationship of $\Delta\mathcal{P}$ and $\Delta\Phi$ is:

$\displaystyle\Delta\mathcal{P}({\mathcal{S}}_{1},{\mathcal{S}}_{2})$
$\displaystyle=\mathcal{P}({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})-\mathcal{P}({\mathcal{S}}_{1})=\mathcal{R}({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})-\mathcal{R}({\mathcal{S}}_{1})-B\cdot\Phi({\mathcal{S}}_{1}\cup{\mathcal{S}}_{2})+B\cdot\Phi({\mathcal{S}}_{1})$
$\displaystyle=\mathcal{R}({\mathcal{S}}_{2})-B\cdot\Delta\Phi({\mathcal{S}}_{1},{\mathcal{S}}_{2}).$

Similarly, on a sample path, we have that
$\Delta\mathcal{P}_{\omega}({\mathcal{S}}_{1},{\mathcal{S}}_{2})=\mathcal{R}({\mathcal{S}}_{2})-B\cdot\Delta\Phi_{\omega}({\mathcal{S}}_{1},{\mathcal{S}}_{2})$.

Let ${\mathcal{S}}(t):=\\{j\in{\mathcal{S}}\mid d_{j}=t\\}$. Given a (partial)
solution ${\mathcal{S}}$ and a sample path of capacities
$\omega=\\{c_{t}\\}_{t=1}^{T}\in\Omega$. We let $a_{t}:=c_{t}-c_{t-1}$, and
the available leftover capacity at time $t$ (after including items in
${\mathcal{S}}(t)$) is

$\max\left\\{\sup_{t^{\prime}\leq
t}\sum_{\tau=t^{\prime}}^{t}a_{\tau}-\mathcal{Q}(S(\tau)),0\right\\}:=\mathcal{C}^{\mathcal{S}}_{\omega}(t).$

Then, overflow units at time $t$ is

$\max\left\\{\sup_{t^{\prime}\leq
t}\mathcal{Q}(S(\tau))-\sum_{\tau=t^{\prime}}^{t}a_{\tau},0\right\\}:=\Phi_{\omega}^{\mathcal{S}}(t),$

and the total overflow units is
$\Phi_{\omega}({\mathcal{S}})=\sum_{t=1}^{T}\Phi_{\omega}^{\mathcal{S}}(t)$.

With the above definitions, we first consider the calculation of overflows on
a set ${\mathcal{S}}$ of items for a given sample path $\omega$. This is done
in Algorithm 7.

Algorithm 7 Overflow Assignment

1:Parameters: Sample path of capacities
$(c_{1},\ldots,c_{T})\in\mathbb{N}^{T}$, an arbitrary ordered list of requests
$\mathcal{L}=(d_{1},d_{2},\ldots,d_{n})$

2:Initialize: Remaining capacity
$\mathbf{a}^{r}=(a_{1}^{r},\ldots,a_{T}^{r})\leftarrow(a_{1},\ldots,a_{T})$
$\triangleright$ $a_{t}=c_{t}-c_{t-1}$

3:Initialize: Units of overflow needing to pay penalty $\Phi\leftarrow 0$

4:$i\leftarrow 1$

5:while $i\leq n$ do

6: $q^{r}\leftarrow q_{i}$

7: $t_{i}=\max\\{t\leq d_{i}:a_{t}^{r}>0\\}$

8: while $q^{r}>0$ do

9: if $t_{i}<\infty$ and $t_{i}>0$ then

10: $a_{t_{i}}^{r}\leftarrow
a_{t_{i}}^{r}-\min\left\\{a^{r}_{t_{i}},q^{r}\right\\}$

11: $q^{r}\leftarrow q^{r}-\min\left\\{a^{r}_{t_{i}},q^{r}\right\\}$

12: $t_{i}\leftarrow t_{i}-1$

13: else

14: $\Phi\leftarrow\Phi+q^{r}$

15: $q^{r}\leftarrow 0$

16: end if

17: end while

18: $i\leftarrow i+1$

19:end while

20:Return $(\mathbf{a}^{r},\Phi)$

Algorithm 7 serves dual purpose – while calculating the overflow, it also
implicitly finds an assignment of the items which do not suffer a penalty to
supply units. The assignment of items to supply units can be non-unique, while
Algorithm 7 identifies one way of matching. Intuitively, the algorithm assigns
items to the latest available units, saving the earlier capacity for items
with shorter deadlines. This allows us to find the total overflows by
considering the items in an arbitrary order (instead of in increasing order of
deadlines), which is in turn useful for finding incremental profit
$\Delta\mathcal{P}$ when we add a set of requests to an existing set of
accepted requests. We begin with the following lemma which proves that
Algorithm 7 indeed finds the minimum overflow.

######  Lemma 8.

Given a sample path $\omega\in\mathbb{N}^{T}$ of supply, and a set
${\mathcal{S}}$ of items with general integer demands, let
$\mathcal{L}=(d_{1},\ldots,d_{n})$ be an arbitrary ordering of the items in
${\mathcal{S}}$ ($d_{i}$ denoting the deadlines). Then the overflow units
$\Phi$ returned when executing Algorithm 7 (Overflow Assignment) on
$(\omega,\mathcal{L})$ satisfies $\Phi=\Phi_{\omega}({{\mathcal{S}}})$.

###### Proof of Lemma 8.

We will use LP duality to prove the Lemma. In a nutshell, we will use the the
assignment created by Algorithm 7 to create a feasible solution to the dual LP
such that the objective function of the dual matches the objective function
penalty of the assignment. Since any feasible solution of the dual lower
bounds the optimal, we would have thus demonstrated the optimality of the
assignment and hence of the overflow units $\Phi$.

$\displaystyle\begin{array}[]{rl}&\mbox{(PRIMAL)}\\\
\min&\sum_{i=1}^{n}y_{i}\\\ \mbox{s.t.}&\\\ \forall
t\in[T]:&-\sum_{i:d_{i}\leq t}x_{i}\geq-c_{t}\\\ \forall
i\in[n]:&x_{i}+y_{i}=q_{i}\\\ &x_{i},y_{i}\geq 0\end{array}\hskip
14.45377pt\left|\hskip 14.45377pt\begin{array}[]{rl}&\mbox{(DUAL)}\\\
\max&\sum_{i=1}^{n}q_{i}\gamma_{i}-\sum_{t}\lambda_{t}c_{t}\\\ \mbox{s.t.}&\\\
\forall i\in[n]:&\gamma_{i}\leq 1\\\ \forall
i\in[n]:&\gamma_{i}\leq\sum_{t\geq d_{i}}\lambda_{t}\\\ &\lambda_{t}\geq
0\end{array}\right.$

To construct the dual solution, let $\tau=\min\\{t:a_{t}^{r}>0\\}$. That is,
$\tau$ is the first time at which there is some capacity remaining after the
assignment of Overflow Assignment. By the nature of the algorithm, there are
no items with $d_{i}\geq\tau$ for which penalty is paid, and in fact all items
with $d_{i}\geq\tau$ are served with capacity that arrives at time $\tau$ or
later. Therefore, the overflow units under the assignment is the total size of
items with $d_{i}<\tau$ minus the capacity $c_{\tau-1}$ (since this capacity
is only used by requests with $d_{i}<\tau$).

Now construct a dual solution as follows:

$\displaystyle\lambda_{t}=\begin{cases}1&t=\tau-1,\\\
0&t\neq\tau-1;\end{cases}\qquad\gamma_{i}=\begin{cases}1&d_{i}\leq\tau-1,\\\
0&d_{i}\geq\tau.\end{cases}$

It is easy to verify that this is a feasible dual solution. Further, the
objective function value under this feasible dual is

$\sum_{i:d_{i}\leq\tau-1}q_{i}-c_{\tau-1}$

which is exactly the overflow units of the primal assignment. Therefore, the
primal solution in fact attains the optimal objective. ∎

As a result of Algorithm 7 and Lemma 8, we have the following lemma.

######  Lemma 9.

Let ${{\mathcal{S}}}$ be a set of items disjoint with ${\mathcal{S}}_{1}$ and
${\mathcal{S}}_{2}$. If for some $\omega=\\{c_{t}\mid t\in[T]\\}\in\Omega$, we
have
$\mathcal{C}_{\omega}^{{\mathcal{S}}_{1}}(t)\geq\mathcal{C}_{\omega}^{{\mathcal{S}}_{2}}(t),\forall
t\in[T]$, then,
$\Delta\mathcal{P}_{\omega}({\mathcal{S}}_{1},{{\mathcal{S}}})\geq\Delta\mathcal{P}_{\omega}({\mathcal{S}}_{2},{{\mathcal{S}}})$.
If this is true for all $\omega\in\Omega$, we further have that
$\Delta\mathcal{P}({\mathcal{S}}_{1},{{\mathcal{S}}})\geq\Delta\mathcal{P}({\mathcal{S}}_{2},{{\mathcal{S}}})$.

###### Proof of Lemma 9.

It suffices to show that
$\Delta\Phi_{\omega}({\mathcal{S}}_{1},{\mathcal{S}})\leq\Delta\Phi({\mathcal{S}}_{2},{\mathcal{S}})$.
Note that

$\displaystyle\Delta\Phi_{\omega}({\mathcal{S}}_{1},{\mathcal{S}})$
$\displaystyle=\Phi_{\omega^{\prime}}({\mathcal{S}}),\text{ where
}\omega^{\prime}=\left\\{\mathcal{C}^{{\mathcal{S}}_{1}}_{\omega}(t)\mid
t\in[T]\right\\},$
$\displaystyle\Delta\Phi_{\omega}({\mathcal{S}}_{2},{\mathcal{S}})$
$\displaystyle=\Phi_{\omega^{\prime\prime}}({\mathcal{S}}),\text{ where
}\omega^{\prime\prime}=\left\\{\mathcal{C}^{{\mathcal{S}}_{2}}_{\omega}(t)\mid
t\in[T]\right\\}.$

By Lemma 8, the ordering of items in ${\mathcal{S}}$ does not matter when
computing the total overflow units, and we may apply Algorithm 7 to compute
$\Phi_{\omega^{\prime}}({\mathcal{S}})$ and
$\Phi_{\omega^{\prime\prime}}({\mathcal{S}})$. Since
$\mathcal{C}_{\omega}^{{\mathcal{S}}_{1}}(t)\geq\mathcal{C}_{\omega}^{{\mathcal{S}}_{2}}(t),\forall
t\in[T]$, as we apply Algorithm 7, for any capacity in $\omega^{\prime\prime}$
that is used to serve a unit of demand in ${\mathcal{S}}$, we have the same
capacity in $\omega^{\prime}$ that can be used to serve the same unit of
demand in ${\mathcal{S}}$. It then follows that
$\Phi_{\omega^{\prime}}({\mathcal{S}})\leq\Phi_{\omega^{\prime\prime}}({\mathcal{S}})$,
which implies that
$\Delta\Phi_{\omega}({\mathcal{S}}_{1},{\mathcal{S}})\leq\Delta\Phi_{\omega}({\mathcal{S}}_{2},{\mathcal{S}})$.
∎

We next show the submodularity of $\mathcal{P}$.

######  Lemma 10.

For any ${\mathcal{S}}_{1}\subseteq{\mathcal{S}}_{2}$, we have that
$\Delta\mathcal{P}({\mathcal{S}}_{1},{\mathcal{S}}_{3})\geq\Delta\mathcal{P}({\mathcal{S}}_{2},{\mathcal{S}}_{3})$.

###### Proof of Lemma 10.

Since ${\mathcal{S}}_{1}\subseteq{\mathcal{S}}_{2}$, in each realized sample
path of capacities $\omega=\\{c_{t}\\}_{t=1}^{T}$, it should be clear that
$\mathcal{C}_{\omega}^{{\mathcal{S}}_{1}}(t)\geq\mathcal{C}_{\omega}^{{\mathcal{S}}_{2}}(t),\forall
t$, i.e., at each time period, the available remaining capacity on
${\mathcal{S}}_{1}$ is no less than the available remaining capacity on
${\mathcal{S}}_{2}$. Thus, by Lemma 9, the result follows. ∎

Lemma 9 and Lemma 10 showed the relationship of incremental profit change of
adding a set of items on top of two other sets of items. Specifically, if one
set always has more remaining capacity than the other set, then adding a third
set to one generates more incremental profit than adding the same set to the
other.

For the rest of this section, we impose the assumption that $q_{i}=q,\forall
i\in[N]$. To simplify the presentation, we may without loss of generality
assume that $q=1$ by allowing $\\{c_{t}\\}$ to be nonintegers. We next have
the following result which will serve as a key to prove Theorem 5.

######  Lemma 11.

Let ${\mathcal{S}}_{1}$ and
${\mathcal{S}}_{2}={{\mathcal{S}}}_{2}^{-}\sqcup{{\mathcal{S}}}_{2}^{+}$ be
two disjoint set of items. Let $i,j,k$ be three items not in either set such
that:

  1. 1.

$d_{m}\leq d_{j}\leq d_{i}$, for all items $m\in{\mathcal{S}}_{2}^{-}$,

  2. 2.

$d_{i}\leq d_{k}\leq d_{m}$, for all items $m\in{\mathcal{S}}_{2}^{+}$.

Then, we have that

$\displaystyle\Delta\mathcal{P}\left({\mathcal{S}}_{1}\cup\\{j,k\\},{\mathcal{S}}_{2}\right)\leq\Delta\mathcal{P}\left({\mathcal{S}}_{1}\cup\\{i\\},{\mathcal{S}}_{2}\right).$
(17)

###### Proof of Lemma 11.

We begin with two observations.
Observation 1: Using Lemma 8, we can determine
$\Delta\mathcal{P}\left({\mathcal{S}}_{1}\cup\\{j,k\\},{\mathcal{S}}_{2}\right)$
as follows: We first fix an ordering of ${\mathcal{S}}_{1}$ and assign them
using Algorithm 7. This gives some residual capacity vector $\mathbf{c}^{r}$.
The problem of finding
$\Delta\mathcal{P}({\mathcal{S}}_{1}\cup\\{j,k\\},{\mathcal{S}}_{2})$ under
capacity vector $\omega$ now reduces to finding
$\Delta\mathcal{P}(\\{j,k\\},{\mathcal{S}}_{2})$ under capacity vector
$\mathbf{c}^{r}$. Similarly, finding
$\Delta\mathcal{P}({\mathcal{S}}_{1}\cup\\{i\\},{\mathcal{S}}_{2})$ under
capacity vector $\omega$ reduces to finding
$\Delta\mathcal{P}(\\{i\\},{\mathcal{S}}_{2})$ under capacity vector
$\mathbf{c}^{r}$.

Observation 2: It suffices to prove the Lemma for $|{\mathcal{S}}_{2}|=1$.

We therefore consider two cases, based on whether the item $m$ in $S_{2}$ has
$d_{m}\leq d_{j}\leq d_{i}$ or $d_{m}\geq d_{k}\geq d_{i}$. Note that we have
reduced to a case where we only need to worry about items $i,j,k,m$ and
capacity availability $\mathbf{c}^{r}$.

Case : $d_{m}\leq d_{j}\leq d_{i}$
To find incremental penalty:

$\Phi^{\\{i,m\\}}_{\mathbf{c}^{r}}-\Phi^{\\{i\\}}_{\mathbf{c}^{r}}$

we will first add item $i$ and then $m$ according to Algorithm 7. Similarly,
for

$\Phi^{\\{j,k,m\\}}_{\mathbf{c}^{r}}-\Phi^{\\{j,k\\}}_{\mathbf{c}^{r}}$

we first add item $j$, then $k$ and then $m$. We claim that if item $m$ does
not pay a penalty in the latter case (when added to $\\{j,k\\}$), then it does
not pay a penalty when added to $\\{i\\}$. To see why, if $m$ does not pay a
penalty when added to $\\{j,k\\}$, then it must be that

$\sum_{t\leq d_{j}}c_{t}^{r}\geq 2,\quad\sum_{t\leq d_{m}}c_{t}^{r}\geq 1.$

In this case, when adding item $i$, there is still residual capacity left for
matching $m$.

Case : $d_{i}\leq d_{k}\leq d_{m}$
In this we argue that if $m$ pays a penalty when added to $i$, then it must
pay a penalty when added to $\\{j,k\\}$. If $m$ pays penalty for $i$, then:

$\sum_{t\leq d_{i}}c_{t}^{r}\leq 1,\quad\sum_{d_{i}<t\leq d_{m}}c_{t}^{r}=0.$

In this case when we first add $k$, it uses up any capacity $c_{t}^{r}\leq
d_{i}$, leaving $m$ to pay a penalty.

Therefore, in either case, the incremental overflow units when adding item $m$
to item $i$ is at most the incremental overflow units when adding $m$ to
$\\{j,k\\}$. ∎

With the above lemmas, we are in a position to prove Theorem 5.

###### Proof of Theorem 5.

First, suppose that without loss of generality, the items in
${\mathcal{S}}_{p}$ are added exactly in the order of $g_{1},\ldots,g_{l}$.
Our proof is done by defining $G_{i}$ and ${\mathcal{S}}^{*}_{i}$ inductively,
and show that

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})\leq
2\mathcal{P}(G_{i})+\Delta\mathcal{P}(G_{i},{\mathcal{S}}^{*}_{i}),\quad\forall
i\leq\min\\{l,m\\}\text{ s.t. }{\mathcal{S}}_{i}^{*}\text{ is well-defined}.$

_Base Case._ Let $G_{1}=\\{g_{1}\\}$ and let
${\mathcal{S}}^{*}={{\mathcal{S}}^{*}}^{-}\sqcup{{\mathcal{S}}^{*}}^{+}$ where
${{\mathcal{S}}^{*}}^{-}:=\\{j\in{\mathcal{S}}^{*}\mid d_{j}<d_{g_{1}}\\}$ and
${{\mathcal{S}}^{*}}^{+}:=\\{j\in{\mathcal{S}}^{*}\mid d_{j}\geq
d_{g_{1}}\\}$. Define

$\displaystyle{\mathcal{S}}^{*}_{1}=\begin{cases}{\mathcal{S}}^{*}\setminus\\{g_{1}\\},\quad\text{if
}g_{1}\in{\mathcal{S}}^{*}\\\
{\mathcal{S}}^{*}\setminus\\{o^{\prime},o^{\prime\prime}\\},\quad\text{if
}g_{1}\notin{\mathcal{S}}^{*}\end{cases}$

where $o^{\prime}\in{\mathcal{S}}^{*}:d_{i^{\prime}}\leq d_{o^{\prime}}\leq
d_{g_{1}},\forall i^{\prime}\in{{\mathcal{S}}^{*}}^{-}$, and
$o^{\prime\prime}\in{\mathcal{S}}^{*}:d_{g_{1}}\leq d_{o^{\prime}}\leq
d_{j^{\prime}},\forall j^{\prime}\in{{\mathcal{S}}^{*}}^{+},$ i.e.,
$o^{\prime}$ is an item in ${\mathcal{S}}^{*}$ with deadline no later than
$g_{1}$ but no earlier than the deadlines of items in
${{\mathcal{S}}^{*}}^{-}$, and $o^{\prime\prime}$ is an item in
${\mathcal{S}}^{*}$ with deadline no earlier than $g_{1}$ but no later than
the deadlines of items in ${{\mathcal{S}}^{*}}^{+}_{i}$ (if such $o^{\prime}$
or $o^{\prime\prime}$ does not exist, then simply ignore it). Then, we have
the two cases:

  * •

$g_{1}\in{\mathcal{S}}^{*}$.

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})=\Delta\mathcal{P}\left(\emptyset,{\mathcal{S}}^{*}\right)$
$\displaystyle=\Delta\mathcal{P}\left(\emptyset,\\{g_{1}\\}\right)+\Delta\mathcal{P}\left(\\{g_{1}\\},{\mathcal{S}}_{1}^{*}\right)$
$\displaystyle\leq
2\mathcal{P}(G_{1})+\Delta\mathcal{P}(G_{1},{\mathcal{S}}^{*}_{1})$

where the inequality follows directly from the fact that
$\mathcal{P}(G_{1})=\Delta\mathcal{P}\left(\emptyset,\\{g_{1}\\}\right)$ is
nonnegative.

  * •

$g_{1}\notin{\mathcal{S}}^{*}$. First note that

$\displaystyle\Delta\mathcal{P}\left(\emptyset,\left\\{o^{\prime},o^{\prime\prime}\right\\}\right)$
$\displaystyle=\Delta\mathcal{P}\left(\emptyset,\\{o^{\prime}\\}\right)+\Delta\mathcal{P}\left(\\{o^{\prime}\\},\\{o^{\prime\prime}\\}\right)$
$\displaystyle\leq\Delta\mathcal{P}\left(\emptyset,\\{o^{\prime}\\}\right)+\Delta\mathcal{P}\left(\emptyset,\\{o^{\prime\prime}\\}\right)$
$\displaystyle\leq\Delta\mathcal{P}(\emptyset,\\{g_{1}\\})+\Delta\mathcal{P}(\emptyset,\\{g_{1}\\})=2\Delta\mathcal{P}(\emptyset,\\{g_{1}\\})=2\mathcal{P}(G_{1}),$

where the first inequality follows from Lemma 10 and the second inequality
follows from the greedy algorithm that $g_{1}$ gives the greatest incremental
profit.

On the other hand, by Lemma 11, we also have that

$\displaystyle\Delta\mathcal{P}\left(\left\\{o^{\prime},o^{\prime\prime}\right\\},{\mathcal{S}}_{1}^{*}\right)\leq\Delta\mathcal{P}\left(G_{1},{\mathcal{S}}^{*}_{1}\right).$

Combining the above two inequalities, we conclude that

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})=\Delta\mathcal{P}\left(\emptyset,{\mathcal{S}}^{*}\right)$
$\displaystyle=\Delta\mathcal{P}\left(\emptyset,\left\\{o^{\prime},o^{\prime\prime}\right\\}\right)+\Delta\mathcal{P}\left(\left\\{o^{\prime},o^{\prime\prime}\right\\},{\mathcal{S}}^{*}_{1}\right)$
$\displaystyle\leq
2\mathcal{P}\left(G_{1}\right)+\Delta\mathcal{P}\left(G_{1},{\mathcal{S}}^{*}_{1}\right)$

_Induction Step._ Assume that $\mathcal{P}({\mathcal{S}}^{*})\leq
2\mathcal{P}(G_{i})+\Delta\mathcal{P}(G_{i},{\mathcal{S}}^{*}_{i})$, we define
$G_{i+1}=G_{i}\cup\\{g_{i+1}\\}$ and let
${\mathcal{S}}^{*}_{i}={{\mathcal{S}}^{*}_{i}}^{-}\sqcup{{\mathcal{S}}^{*}_{i}}^{+}$
where ${{\mathcal{S}}^{*}_{i}}^{-}:=\\{j\in{\mathcal{S}}^{*}_{i}\mid
d_{j}<d_{g_{i}}\\}$ and
${{\mathcal{S}}^{*}_{i}}^{+}:=\\{j\in{\mathcal{S}}^{*}_{i}\mid d_{j}\geq
d_{g_{i}}\\}$. Define

$\displaystyle{\mathcal{S}}^{*}_{i+1}=\begin{cases}{\mathcal{S}}^{*}_{i}\setminus\\{g_{i+1}\\},\quad\text{if
}g_{i+1}\in{\mathcal{S}}^{*}_{i}\\\
{\mathcal{S}}^{*}_{i}\setminus\\{o^{\prime},o^{\prime\prime}\\},\quad\text{if
}g_{i+1}\notin{\mathcal{S}}^{*}_{i}\end{cases}$

where where $o^{\prime}\in{\mathcal{S}}^{*}_{i}:d_{i^{\prime}}\leq
d_{o^{\prime}}\leq d_{g_{i}},\forall
i^{\prime}\in{{\mathcal{S}}^{*}_{i}}^{-}$, and
$o^{\prime\prime}\in{\mathcal{S}}^{*}_{i}:d_{g_{i}}\leq d_{o^{\prime}}\leq
d_{j^{\prime}},\forall j^{\prime}\in{{\mathcal{S}}^{*}_{i}}^{+},$ i.e.,
$o^{\prime}$ is an item in ${\mathcal{S}}^{*}_{i}$ with deadline no later than
$g_{i}$ but no earlier than the deadlines of items in
${{\mathcal{S}}^{*}_{i}}^{-}$, and $o^{\prime\prime}$ is an item in
${\mathcal{S}}^{*}_{i}$ with deadline no earlier than $g_{i}$ but no later
than the deadlines of items in ${{\mathcal{S}}^{*}}^{+}_{i}$ (if such
$o^{\prime}$ or $o^{\prime\prime}$ does not exist, then simply ignore it).
Then, we have in the two cases:

  * •

$g_{i+1}\in{\mathcal{S}}^{*}_{i}$.

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})$ $\displaystyle\leq
2\mathcal{P}(G_{i})+\Delta\mathcal{P}(G_{i},{\mathcal{S}}^{*}_{i})=2\mathcal{P}(G_{i})+\Delta\mathcal{P}\left(G_{i},\left\\{g_{i+1}\right\\}\right)+\Delta\mathcal{P}\left(G_{i+1},{\mathcal{S}}^{*}_{i+1}\right)$
$\displaystyle\leq
2\mathcal{P}(G_{i})+2\Delta\mathcal{P}\left(G_{i},\left\\{g_{i+1}\right\\}\right)+\Delta\mathcal{P}\left(G_{i+1},{\mathcal{S}}^{*}_{i+1}\right)=2\mathcal{P}(G_{i+1})+\Delta\mathcal{P}\left(G_{i+1},{\mathcal{S}}^{*}_{i+1}\right)$

where the first inequality follows from the induction assumption and the
second inequality follows directly from the fact that
$\Delta\mathcal{P}\left(G_{i},\\{g_{i+1}\\}\right)$ is nonnegative.

  * •

$g_{i+1}\notin{\mathcal{S}}^{*}_{i}$. First note that

$\displaystyle\Delta\mathcal{P}\left(G_{i},\left\\{o^{\prime},o^{\prime\prime}\right\\}\right)$
$\displaystyle=\Delta\mathcal{P}\left(G_{i},\\{o^{\prime}\\}\right)+\Delta\mathcal{P}\left(G_{i}\cup\\{o^{\prime}\\},\\{o^{\prime\prime}\\}\right)$
$\displaystyle\leq\Delta\mathcal{P}\left(G_{i},\\{o^{\prime}\\}\right)+\Delta\mathcal{P}\left(G_{i},\\{o^{\prime\prime}\\}\right)$
$\displaystyle\leq\Delta\mathcal{P}(G_{i},\\{g_{i+1}\\})+\Delta\mathcal{P}(G_{i},\\{g_{i+1}\\})=2\Delta\mathcal{P}(G_{i},\\{g_{i+1}\\}),$

where the first inequality follows from Lemma 10 and the second inequality
follows from the greedy algorithm that $g_{i+1}$ adds the greatest incremental
profit to $G_{i}$.

On the other hand, by Lemma 11, we also have that

$\displaystyle\Delta\mathcal{P}\left(G_{i}\cup\left\\{o^{\prime},o^{\prime\prime}\right\\},{\mathcal{S}}_{i+1}^{*}\right)\leq\Delta\mathcal{P}\left(G_{i+1},{\mathcal{S}}^{*}_{i+1}\right).$

Combining the above two inequalities, we conclude that

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})$ $\displaystyle\leq
2\mathcal{P}(G_{i})+\Delta\mathcal{P}(G_{i},{\mathcal{S}}^{*}_{i})=2\mathcal{P}(G_{i})+\Delta\mathcal{P}\left(G_{i},\left\\{o^{\prime},o^{\prime\prime}\right\\}\right)+\Delta\mathcal{P}\left(G_{i}\cup\left\\{o^{\prime},o^{\prime\prime}\right\\},{\mathcal{S}}^{*}_{i+1}\right)$
$\displaystyle\leq
2\mathcal{P}(G_{i})+2\Delta\mathcal{P}\left(G_{i},\left\\{g_{i+1}\right\\}\right)+\Delta\mathcal{P}\left(G_{i+1},{\mathcal{S}}^{*}_{i+1}\right)$
$\displaystyle\leq
2\mathcal{P}\left(G_{i+1}\right)+\Delta\mathcal{P}\left(G_{i+1},{\mathcal{S}}^{*}_{i+1}\right)$

This completes the induction step. Note that at each step,
${\mathcal{S}}^{*}_{i+1}\subsetneq{\mathcal{S}}^{*}_{i}$ and $G_{i}\subsetneq
G_{i+1}$. In the end, we will reach some $i^{\prime}$ such that either
${\mathcal{S}}^{*}_{i^{\prime}}=\emptyset$ or
$G_{i^{\prime}}={\mathcal{S}}_{p}$ and
${\mathcal{S}}^{*}_{i^{\prime}}\neq\emptyset$. In the first case, we have that

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})$ $\displaystyle\leq
2\mathcal{P}(G_{i^{\prime}})+\Delta\mathcal{P}(G_{i^{\prime}},{\mathcal{S}}^{*}_{i^{\prime}})=2\mathcal{P}(G_{i^{\prime}})+0\leq
2\mathcal{P}({\mathcal{S}}_{p}).$

In the second case, i.e., $G_{i^{\prime}}={\mathcal{S}}_{p}$ and
${\mathcal{S}}^{*}_{i^{\prime}}\neq\emptyset$, we again have that
$\mathcal{P}({\mathcal{S}}^{*})\leq
2\mathcal{P}(G_{i^{\prime}})+\Delta\mathcal{P}(G_{i^{\prime}},{\mathcal{S}}^{*}_{i^{\prime}})$.
Now if $\Delta\mathcal{P}(G_{i^{\prime}},{\mathcal{S}}^{*}_{i^{\prime}})>0$,
then we can add the items in ${\mathcal{S}}^{*}_{i^{\prime}}$ to
${\mathcal{S}}_{p}$ and still increase the profit, which violates the greedy
algorithm. Thus, it must be that
$\Delta\mathcal{P}(G_{i^{\prime}},{\mathcal{S}}^{*}_{i^{\prime}})\leq 0$. Then
we would have

$\displaystyle\mathcal{P}({\mathcal{S}}^{*})$ $\displaystyle\leq
2\mathcal{P}(G_{i^{\prime}})+\Delta\mathcal{P}(G_{i^{\prime}},{\mathcal{S}}^{*}_{i^{\prime}})\leq
2\mathcal{P}({\mathcal{S}}_{p}).$

In conclusion, we have that $\mathcal{P}({\mathcal{S}}^{*})\leq
2\mathcal{P}({\mathcal{S}}_{p})$, or equivalently
$\mathcal{P}({\mathcal{S}}_{p})\geq\frac{1}{2}\mathcal{P}({\mathcal{S}}^{*})$.
This completes the proof of Theorem 5. ∎

##  Appendix B Alternative FPTAS for MPBKP

In this section, we introduce another FPTAS for MPBKP, which has time
complexity $\tilde{\mathcal{O}}\left(n+\frac{T^{2}}{\epsilon^{3}}\right)$. To
roughly describe the main idea, we will again adopt the functional approach to
approximate (6). Instead of having an approximation of $f_{\mathcal{I}(t)}$
for each $t$ directly from Lemma 1, we further partition $\mathcal{I}(t)$ into
$m+1$ subsets ($m$ being specified later), i.e.,
$\mathcal{I}(t):=\mathcal{I}(t)_{0}\sqcup\mathcal{I}(t)_{1}\sqcup\cdots\sqcup\mathcal{I}(t)_{m}$,
where items in each subset have approximately the same reward. Then, we have
that $f_{\mathcal{I}(t)}=f_{\mathcal{I}(t)_{0}}\oplus
f_{\mathcal{I}(t)_{1}}\oplus\cdots\oplus
f_{\mathcal{I}(t)_{m}}:=\oplus_{j=0}^{m}f_{\mathcal{I}(t)_{j}}$, and by noting
that the $(\max,+)$-convolution $\oplus$ is commutative, the function $f_{t}$
as defined in (6) can be computed as

$\displaystyle f_{t}:=\begin{cases}f_{\mathcal{I}(1)}^{c_{1}}&t=1,\\\
\left(f_{t-1}\oplus f_{\mathcal{I}(t)}\right)^{c_{t}}=\left(f_{t-1}\oplus
f_{\mathcal{I}(t)_{0}}\oplus f_{\mathcal{I}(t)_{1}}\oplus\cdots\oplus
f_{\mathcal{I}(t)_{m}}\right)^{c_{t}}&t\geq 2,\end{cases}$ (18)

and (18) can be computed more efficiently due to some special properties of
$f_{\mathcal{I}(t)_{j}}$.

Before proceeding to the actual algorithm, we first have some preliminaries. A
monotone step function $f_{\mathcal{I}}(c)$ with steps at
$c_{1},c_{2},\ldots,c_{l}$ is called _$r$ -uniform_ if it satisfies both of
the following conditions:

  1. 1.

$\forall c\in\mathbb{R}^{+}$, $f_{\mathcal{I}}(c)=kr$ for some nonnegative
integer $k$,

  2. 2.

$\exists c_{j}\text{ s.t. }f_{\mathcal{I}}(c_{j})=kr\Longrightarrow\exists
c_{j^{\prime}}\text{ s.t. }f_{\mathcal{I}}(c_{j^{\prime}})=k^{\prime}r,\forall
k^{\prime}\leq k$ nonnegative integers.

The monotone step function $f_{\mathcal{I}}(c)$ with steps at
$c_{1},c_{2},\ldots,c_{l}$ is called _pseudo-concave_ if $c_{j+2}-c_{j+1}\geq
c_{j+1}-c_{j},\forall j=1,\ldots,l-2$. The _range_ of a function $f$ is the
set of all possible function values. We then introduce the following lemma
from Chan,  (2018) for approximating $f\oplus g$ when $g$ is $r$-uniform and
pseudo-concave.

######  Lemma 12 (Chan,  (2018)).

Let $f$ and $g$ be monotone step functions with total complexity $l$ and
ranges contained in $\\{-\infty,0\\}\cup\\{A,B\\}$. Then we can compute a
monotone step function that approximates $f\oplus g$ with factor
$1+\mathcal{O}(\epsilon^{\prime})$ and complexity
$\tilde{\mathcal{O}}\left(\frac{1}{\epsilon^{\prime}}\right)$ in
$\mathcal{O}(l)+\tilde{\mathcal{O}}\left(\frac{1}{\epsilon^{\prime}}\right)$
time if $g$ is $r$-uniform and pseudo-concave.

With the above lemma, we present Algorithm 8 for MPBKP.

Algorithm 8 FPTAS for MPBKP in
$\tilde{\mathcal{O}}\left(n+T^{2}/\epsilon^{3}\right)$

1:Input: $[n],c_{1},\ldots,c_{T}$ $\triangleright$ Set of items to be packed,
cumulative capacities up to each time $t$

2:Output: $\tilde{f}_{t}$ $\triangleright$ Approximation of function $f_{t}$

3:Discard all items with $r_{i}\leq\frac{\epsilon}{n}\max_{j}r_{j}$ and
relabel the items

4:$r_{0}\leftarrow\min_{i}r_{i}$ $\triangleright$ Lower bound of solution
value

5:$\hat{r}_{i}\leftarrow
r_{0}\cdot(1+\epsilon)^{\left\lfloor\log_{1+\epsilon}\left(\frac{r_{i}}{r_{0}}\right)\right\rfloor}$
$\triangleright$ Round down the reward of each item

6:$m\leftarrow\left\lceil\log_{1+\epsilon}\frac{n^{2}}{\epsilon}\right\rceil$
$\triangleright$ Number of distinct rewards to be considered, each in the form
$r_{0}\cdot(1+\epsilon)^{k}$

7:$\tilde{f}_{0}\leftarrow-\infty$

8:for $t=1,\ldots,T$ do

9: $\hat{f}_{t}\leftarrow\tilde{f}_{t-1}$

10: for $j=0,\ldots,m$ do

11:
$\mathcal{I}(t)_{j}=\left\\{i\in\mathcal{I}(t)\mid\hat{r}_{i}=r_{0}\cdot(1+\epsilon)^{j}\right\\}$
$\triangleright$ Items in each $\mathcal{I}(t)_{j}$ has the same rounded
reward

12: $\hat{\mathcal{I}}(t)_{j}=\left\\{(\hat{r}_{i},q_{i})\mid
i\in\mathcal{I}(t)_{j}\right\\}$ and obtain $f_{\hat{\mathcal{I}}(t)_{j}}$
$\triangleright$ Using items with rounded rewards, build the function
$f_{\hat{\mathcal{I}}(t)_{j}}$

13: Approximately compute $\hat{f}_{t}=\hat{f}_{t}\oplus
f_{\hat{\mathcal{I}}(t)_{j}}$ using Lemma 12

14: end for

15: $\tilde{f}_{t}=\hat{f}_{t}^{c_{t}}$ $\triangleright$ $\tilde{f}_{t}$ is an
approximation of $f_{t}$

16:end for

In Algorithm 8, we first discard all items with reward
$r_{i}\leq\frac{\epsilon}{n}\max_{j}r_{j}$. The maximum we could lose is
$n\cdot\frac{\epsilon}{n}\max_{j}r_{j}=\epsilon\max_{j}r_{j}$, which is at
most $\epsilon$ fraction of the optimal value. We next round down the rewards
of all remaining items to the nearest $r_{0}\cdot(1+\epsilon)^{k}$, where
$r_{0}:=\min_{j}r_{j}$ and $k$ is some nonnegative integer, so we lose at most
a fraction of $(1+\epsilon)$ in the rounding, and the number of distinct
rounded rewards is bounded by
$m=\left\lceil\log_{1+\epsilon}\frac{n^{2}}{\epsilon}\right\rceil=\tilde{\mathcal{O}}\left(\frac{1}{\epsilon}\right)$.
We begin with initializing $\tilde{f}_{0}=-\infty$. Then, for period $t=1$, we
partition $\mathcal{I}(1)=\sqcup_{j=0}^{m}\mathcal{I}(1)_{j}$ where all items
in $\mathcal{I}(1)_{j}$ have rounded reward $r_{0}\cdot(1+\epsilon)^{j}$.
Denote by $\hat{\mathcal{I}}(1)_{j}$ these items with rounded rewards, and by
adding these items greedily in nonincreasing order of their sizes, we obtain
$f_{\hat{\mathcal{I}}(1)_{j}}$, which is a $(1+\epsilon)$ approximation of
$f_{\mathcal{I}(1)_{j}}$, and is $r_{0}\cdot(1+\epsilon)^{j}$-uniform and
pseudo-concave. By applying Lemma 12 for $m+1$ times (with $\epsilon^{\prime}$
to be specified later), we obtain $\tilde{f}_{0}\oplus
f_{\hat{\mathcal{I}}(1)_{0}}\oplus
f_{\hat{\mathcal{I}}(1)_{1}}\oplus\cdots\oplus
f_{\mathcal{I}(1)_{m}}=\tilde{f}_{0}\oplus f_{\hat{\mathcal{I}}(1)}$, which
approximates $f_{0}\oplus f_{\mathcal{I}(1)}$ with an accumulative
approximation factor $(1+\epsilon)(1+\epsilon^{\prime})^{m+1}$, and is
computed in total time
$\mathcal{O}(n_{1})+\tilde{\mathcal{O}}\left(\frac{m+1}{\epsilon^{\prime}}\right)$.
Then, to ensure feasibility, $\tilde{f}_{1}$ is obtained by taking truncation
$c_{1}$ on $\tilde{f}_{0}\oplus f_{\hat{\mathcal{I}}(1)}$, which becomes a
$(1+\epsilon)(1+\epsilon^{\prime})^{m+1}$ approximation of $f_{1}$. We then
move to period $2$ and continue this pattern of partition, convolutions, and
truncation. In the end as we reach period $T$, $\tilde{f}_{T}$ would only
contain feasible solutions to (1), and approximates $f_{T}$ with accumulated
approximation factor
$(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)T}\approx(1+\epsilon)(1+(m+1)T\epsilon^{\prime})$.
Formally, we have the following lemma which shows the approximation factor of
$\tilde{f}_{t}$ to $f_{t}$.

######  Lemma 13.

Let $\tilde{f}_{t}$ be the functions obtained from Algorithm 8, and let
$f_{t}$ be defined as in (6). Then, $\tilde{f}_{t}$ approximates $f_{t}$ with
factor $(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)t}$, i.e.,
$\tilde{f}_{t}(c)\leq
f_{t}(c)\leq(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)t}\tilde{f}_{t}(c)$ for
all $0\leq c\leq c_{t}$.

The proof of Lemma 13 relies on the following fact.

######  Lemma 14.

At any period $t$, after running the inner “for” loop of Algorithm 8, we have
that $(1+\epsilon^{\prime})^{m+1}\hat{f}_{t}\geq\tilde{f}_{t-1}\oplus
f_{\hat{\mathcal{I}}(t)_{0}}\oplus
f_{\hat{\mathcal{I}}(t)_{1}}\oplus\cdots\oplus f_{\hat{\mathcal{I}}(t)_{m}}$.

###### Proof of Lemma 14.

We prove by induction on $j=0,1,\ldots,m$. Base case is when $j=0$, i.e.,
after the first round of the inner “for” loop, by Lemma 12, we have that
$(1+\epsilon^{\prime})\hat{f}_{t}\geq\tilde{f}_{t-1}\oplus
f_{\hat{\mathcal{I}}(t)_{0}}$. For the induction step, assume that after $j$
rounds of the inner “for” loop,
$(1+\epsilon^{\prime})^{j}\hat{f}_{t}\geq\tilde{f}_{t-1}\oplus
f_{\hat{\mathcal{I}}(t)_{0}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t)_{j-1}}$, we show that after $j+1$ rounds,
$(1+\epsilon^{\prime})^{j+1}\hat{f}_{t}\geq\tilde{f}_{t-1}\oplus
f_{\hat{\mathcal{I}}(t)_{0}}\oplus\cdots\oplus f_{\hat{\mathcal{I}}(t)_{j}}$.
As a notation, we denote by $\hat{f}_{t}^{\rm old}$ the $\hat{f}_{t}$ right
before the $(j+1)$th round of the inner “for” loop, and by $\hat{f}_{t}^{\rm
new}$ the $\hat{f}_{t}$ right after the $(j+1)$th round of the inner “for”
loop. Then, from Lemma 12 we have that $(1+\epsilon^{\prime})\hat{f}_{t}^{\rm
new}\geq\hat{f}_{t}^{\rm old}\oplus f_{\hat{\mathcal{I}}(t)_{j}},$ which
implies that

$(1+\epsilon^{\prime})^{j+1}\hat{f}_{t}^{\rm
new}\geq(1+\epsilon^{\prime})^{j}\hat{f}_{t}^{\rm old}\oplus
f_{\hat{\mathcal{I}}(t)_{j}}\geq\tilde{f}_{t-1}\oplus
f_{\hat{\mathcal{I}}(t)_{0}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t)_{j-1}}\oplus f_{\hat{\mathcal{I}}(t)_{j}},$

where the second inequality follows from the induction assumption. This
finishes the induction step, and thus the proof of the lemma. ∎

With Lemma 14 at hand, we now prove Lemma 13.

###### Proof of Lemma 13.

By the construction of $\tilde{f}_{t}$, it should be clear that
$\tilde{f}_{t}\leq f_{t}$. We prove that
$(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)t}\tilde{f}_{t}\geq f_{t}$ by
induction on $t$. Base case is when $t=1$, we have that
$(1+\epsilon)(1+\epsilon^{\prime})^{m+1}\tilde{f}_{1}=(1+\epsilon)(1+\epsilon^{\prime})^{m+1}\hat{f}_{1}^{c_{1}}\geq(1+\epsilon)\left(\tilde{f}_{0}\oplus
f_{\hat{\mathcal{I}}(1)}\right)^{c_{1}}=(1+\epsilon)f_{\hat{\mathcal{I}}(1)}^{c_{1}}\geq
f_{\mathcal{I}(1)}^{c_{1}}=f_{1}$, where the first inequality follows from
Lemma 12, and the second inequality follows from the rounding of the rewards.
For the induction step, assume that
$(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)t}\tilde{f}_{t}\geq f_{t}$, we show
that $(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)(t+1)}\tilde{f}_{t+1}\geq
f_{t+1}$.

After partitioning
$\mathcal{I}(t+1)=\mathcal{I}(t+1)_{0}\sqcup\mathcal{I}(t+1)_{1}\sqcup\cdots\sqcup\mathcal{I}(t+1)_{m}$,
for any item $i\in\mathcal{I}(t+1)$, by the rounding down, we have that
$(1+\epsilon)\hat{r}_{i}\geq r_{i}\geq\hat{r}_{i}$, which further implies that
$(1+\epsilon)f_{\hat{\mathcal{I}}(t+1)_{j}}\geq f_{{\mathcal{I}}(t+1)_{j}}\geq
f_{\hat{\mathcal{I}}(t+1)_{j}},\forall j=0,1,\ldots,m$. Thus,

$\displaystyle\quad(1+\epsilon)\left(f_{\hat{\mathcal{I}}(t+1)_{0}}\oplus
f_{\hat{\mathcal{I}}(t+1)_{1}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t+1)_{m}}\right)\geq f_{\mathcal{I}(t+1)}\geq
f_{\hat{\mathcal{I}}(t+1)_{0}}\oplus
f_{\hat{\mathcal{I}}(t+1)_{1}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t+1)_{m}},$

which, together with the induction assumption, implies that

$(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)t}\left(\tilde{f}_{t}\oplus
f_{\hat{\mathcal{I}}(t+1)_{0}}\oplus
f_{\hat{\mathcal{I}}(t+1)_{1}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t+1)_{m}}\right)\geq f_{t}\oplus f_{\mathcal{I}(t+1)}.$

By Lemma 14, after the inner “for” loop in Algorithm 8, we have that
$(1+\epsilon^{\prime})^{m+1}\hat{f}_{t+1}\geq\tilde{f}_{t}\oplus
f_{\hat{\mathcal{I}}(t+1)_{0}}\oplus
f_{\hat{\mathcal{I}}(t+1)_{1}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t+1)_{m}}$, which implies that

$\displaystyle(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)(t+1)}\hat{f}_{t+1}$
$\displaystyle\geq(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)(t+1)}\left(\tilde{f}_{t}\oplus
f_{\hat{\mathcal{I}}(t+1)_{0}}\oplus
f_{\hat{\mathcal{I}}(t+1)_{1}}\oplus\cdots\oplus
f_{\hat{\mathcal{I}}(t+1)_{m}}\right)$ $\displaystyle\geq f_{t}\oplus
f_{\mathcal{I}(t+1)}.$

Taking truncation on both sides, we conclude that

$\displaystyle(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)(t+1)}\tilde{f}_{t+1}$
$\displaystyle=(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)(t+1)}\hat{f}_{t+1}^{c_{t+1}}\geq\left(f_{t}\oplus
f_{\mathcal{I}(t+1)}\right)^{c_{t+1}}=f_{t+1}.$

This finishes the induction step, and thus the proof of the lemma. ∎

Lemma 13 and Proposition 1 together imply that $\tilde{f}_{T}(c_{T})$,
obtained from Algorithm 8, approximates the optimal value of MPBKP (1) by a
factor of
$(1+\epsilon)(1+\epsilon^{\prime})^{(m+1)T}\approx(1+\epsilon+mT\epsilon^{\prime})$.
In Algorithm 8, during each of the periods $t=1,\ldots,T$, approximately
computing the $(\max,+)$-convolutions on
$\hat{f}_{t}\oplus{f}_{\hat{\mathcal{I}}(t)_{j}}$ for all $j=0,1,\ldots,m$
take total time $\tilde{O}\left(n_{t}+(m+1)/\epsilon^{\prime}\right)$.
Therefore, Algorithm 8 has total runtime
$\tilde{O}\left(n+(m+1)T/\epsilon^{\prime}\right)$. As a result, we have the
following proposition.

######  Proposition 4.

Taking $\epsilon=mT\epsilon^{\prime}$ and $m=\tilde{\mathcal{O}}(1/\epsilon)$,
Algorithm 8 achieves $(1+\epsilon)$-approximation for MPBKP in
$\tilde{O}\left(n+\frac{T^{2}}{{\epsilon}^{3}}\right)$.

##  Appendix C Alternative FPTAS for MPBKP-S

In this section, we provide an FPTAS for the MPBKP-S with time complexity
$\mathcal{O}\left(\frac{n^{2}\log n}{\epsilon}\right)$. Following the
classical approach for “0-1” knapsack problems (see, e.g., Vazirani,  (2013)),
we round down the reward of each item so that the optimal solution for the
MPBKP under the new rounded rewards is upper bounded by some polynomial of $n$
and $1/\epsilon$, and thus the naive pseudo-polynomial dynamic program becomes
a polynomial time algorithm.

We assume that the items are initially sorted and relabeled in the increasing
order of their deadlines, i.e., $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$.
Further, assume that we have a guess $P_{0}$ that satisfies (10). Then, we
choose a discretization quantum $\kappa:=\epsilon P_{0}/2n$ and define rounded
rewards $\hat{r}_{i}:=\left\lfloor\frac{r_{i}}{\kappa}\right\rfloor_{\kappa}$.
We then have $\mathcal{P}(\mathcal{S}^{*})\leq\frac{4n}{\epsilon}\kappa$.

For a solution
${\mathcal{S}}={\mathcal{S}}(1)\cup{\mathcal{S}}(2)\cup\cdots\cup{\mathcal{S}}(T)$
where ${\mathcal{S}}(t)$ is the set of items with deadline $t$. Let the items
in ${\mathcal{S}}(t)$ be indexed as
${\mathcal{S}}(t)=\left(i^{(t)}_{1},\ldots,i^{(t)}_{S_{t}}\right)$ in the
order in which Algorithm 9 considers them, we define the rounded profit of
${\mathcal{S}}$ as:

$\displaystyle\hat{\mathcal{P}}({\mathcal{S}})$
$\displaystyle=\hat{\mathcal{R}}({\mathcal{S}})-\sum_{t=1}^{T}\sum_{k=1}^{S_{t}}\left\lceil
B\left(\sum_{\ell\leq k}q_{i^{(t)}_{\ell}}-\max_{0\leq
t^{\prime}<t}\left\\{c_{t}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau<t}\mathcal{Q}({\mathcal{S}}(\tau))\right\\}\right)^{+}\right\rceil_{\kappa}.$
(19)

Let us also define a single period change in rounded profit for a set of items
${\mathcal{S}}=(i_{1},\ldots,i_{S})$ with knapsack capacity $c$ as:

$\displaystyle\Delta\hat{\mathcal{P}}({\mathcal{S}},c)$
$\displaystyle=\hat{\mathcal{R}}({\mathcal{S}})-\sum_{k=1}^{S}\left\lceil
B\left(\sum_{\ell\leq k}q_{i_{\ell}}-c\right)^{+}\right\rceil_{\kappa}.$ (20)

Let $\hat{A}(i,p)$ be the maximum capacity left at time $d_{i}$ when earning
rounded profit at least $p$ using items $\\{1,\ldots,i\\}$ with rounded down
rewards $\hat{r}$, equivalently,

$\displaystyle\hat{A}(i,p):=\max_{\left\\{\begin{subarray}{c}\mathcal{S}\subseteq\\{1,\ldots,i\\}\\\
\hat{\mathcal{P}}(\mathcal{S})\geq p\end{subarray}\right\\}}\max_{0\leq
t^{\prime}<d_{i}}\left\\{c_{d_{i}}-c_{t^{\prime}}-\sum_{t^{\prime}+1\leq\tau\leq
d_{i}-1}\mathcal{Q}({\mathcal{S}}(\tau))\right\\}.$ (21)

If it is not possible to earn profit $p$ at time $d_{i}$ using items
$\\{1,\ldots,i\\}$ with rounded down rewards, i.e., no
$\mathcal{S}\subseteq\\{1,\ldots,i\\}$ exists such that
$\hat{\mathcal{P}}(\mathcal{S})\geq p$, then $\hat{A}(i,p)$ is labeled
$-\infty$. The DP table runs for $i=1,\ldots,n$ and
$p=0,\kappa,\ldots,\left\lceil\frac{4n}{\epsilon}\right\rceil\kappa$. We then
have Algorithm 9, which returns an exact optimal solution of
$\hat{\mathcal{P}}({\mathcal{S}})$ under the rounded rewards and rounded
penalties.

Algorithm 9 DP with rounded down rewards for MPBKP-S

1:Define $\kappa=\frac{\epsilon P_{0}}{2n}$

2:Define $\hat{r}_{i}=\kappa\left\lfloor\frac{r_{i}}{\kappa}\right\rfloor$
$\triangleright$ Round down reward

3:// $\hat{A}(i,p)=$ max capacity left at time $d_{i}$ when earning (rounded)
profit at least $p$ by selecting items in $\\{1,\ldots,i\\}$ with rounded down
rewards $\hat{r}$

4:Initialize $\hat{A}(0,p)=\begin{cases}0&p=0,\\\ -\infty&p>0.\end{cases}$

5:for $t=1,\ldots,T$ do

6: $i=I(t-1)+1$

7: for
$p=\left\\{0,1,\ldots,\left\lceil\frac{4n}{\epsilon}\right\rceil\right\\}\cdot\kappa$
do

8: $\hat{A}(i,p):=\hat{A}(i-1,p)+c_{t}-c_{t-1}$ $\triangleright$ If reject
request $i$

9: end for

10: for
$\bar{p}=\left\\{0,1,\ldots,\left\lceil\frac{4n}{\epsilon}\right\rceil\right\\}\cdot\kappa$
do

11: $p=\bar{p}+\hat{r}_{i}-\left\lceil
B(q_{i}-{\color[rgb]{0,0,0}\max\\{0,\hat{A}(i-1,\bar{p})+(c_{t}-c_{t-1})\\}})^{+}\right\rceil_{\kappa}$

12:
$\hat{A}(i,p)=\max\\{\hat{A}(i,p),\hat{A}(i-1,\bar{p})+(c_{t}-c_{t-1})-q_{i}\\}$
$\triangleright$ Accept $i$

13: end for

14: for
$p=\left\\{\left\lceil\frac{4n}{\epsilon}\right\rceil,\left\lceil\frac{4n}{\epsilon}\right\rceil-1,\ldots,1\right\\}\cdot\kappa$
do

15: if $\hat{A}(i,p-\kappa)<\hat{A}(i,p)$ then

16: $\hat{A}(i,p-\kappa)=\hat{A}(i,p)$

17: end if

18: end for

19: for $i=I(t-1)+2,\ldots,I(t)$ do

20: for
$p=\left\\{0,1,\ldots,\left\lceil\frac{4n}{\epsilon}\right\rceil\right\\}\cdot\kappa$
do

21: $\hat{A}(i,p):=\hat{A}(i-1,p)$ $\triangleright$ If reject request $i$

22: end for

23: for
$\bar{p}=\left\\{0,1,\ldots,\left\lceil\frac{4n}{\epsilon}\right\rceil\right\\}\cdot\kappa$
do

24: ${p}=\bar{p}+\hat{r}_{i}-\left\lceil
B(q_{i}-{\color[rgb]{0,0,0}\max\\{0,\hat{A}(i-1,\bar{p})\\}})^{+}\right\rceil_{\kappa}$

25: $\hat{A}(i,p)=\max\\{\hat{A}(i,p),\hat{A}(i-1,\bar{p})-q_{i}\\}$
$\triangleright$ Accept $i$

26: end for

27: for
$p=\left\\{\left\lceil\frac{4n}{\epsilon}\right\rceil,\left\lceil\frac{4n}{\epsilon}\right\rceil-1,\ldots,1\right\\}\cdot\kappa$
do

28: if $\hat{A}(i,p-\kappa)<\hat{A}(i,p)$ then

29: $\hat{A}(i,p-\kappa)=\hat{A}(i,p)$

30: end if

31: end for

32: end for

33:end for

###### Proof of Correctness of Algorithm 9.

We show that $\hat{A}(i,p)$ returned by the algorithm satisfies (21) by
induction on $i$. The base case ($i=0$) is vacuously true. Now we assume that
(21) holds for all $p\in\left\\{0,1,\ldots,\lceil
4n/\epsilon\rceil\right\\}\kappa$ and for all $k\in[i-1]$. Consider some
$p\in\left\\{0,1,\ldots,\lceil 4n/\epsilon\rceil\right\\}\kappa$, and let
${\mathcal{S}}^{*}$ be any set achieving the maximum in (21) so that
$\hat{\mathcal{P}}({\mathcal{S}})\geq p$. We will show that $\hat{A}(i,p)$ is
at least the leftover capacity under solution ${\mathcal{S}}^{*}$ via case
analysis:

  * •

Case $i\notin{\mathcal{S}}^{*}$: In this case, the leftover capacity under
${\mathcal{S}}^{*}$ is the leftover capacity by $d_{i}$, which is the sum of
leftover capacity in ${\mathcal{S}}^{*}$ by $d_{i-1}$ and
$c_{d_{i}}-c_{d_{i-1}}$. By induction hypothesis, $\hat{A}(i-1,p)$ is no less
than the leftover capacity of ${\mathcal{S}}^{*}$ by $d_{i-1}$, and therefore,
by lines (7,11) and (20,24),
$\hat{A}(i,p)\geq\hat{A}(i-1,p)+c_{d_{i}}-c_{d_{i-1}}$ which in turn is no
less than the leftover capacity under ${\mathcal{S}}^{*}$ by $d_{i}$. By
optimality of ${\mathcal{S}}^{*}$, all the inequalities must be equalities.

  * •

Case $i\in{\mathcal{S}}^{*}$: Let
${\mathcal{S}}^{\prime}={\mathcal{S}}^{*}\setminus\\{i\\}$, and let
$p^{\prime}=\hat{\mathcal{P}}({\mathcal{S}}^{\prime})$ be its rounded profit.
Then by induction hypothesis, $\hat{A}(i-1,p^{\prime})$ is no less than the
leftover capacity under ${\mathcal{S}}^{\prime}$ by $d_{i-1}$. Further, by
packing item $i$ in the solution corresponding to $\hat{A}(i-1,p^{\prime})$,
the change in profit is larger than by packing item $i$ in
${\mathcal{S}}^{\prime}$ (the penalty is no less under
${\mathcal{S}}^{\prime}$ since it has weakly smaller leftover capacity).
Therefore, packing item $i$ in the solution corresponding to
$\hat{A}(i-1,p^{\prime})$ gives a solution with at least as large a rounded
profit as $p$ and at least as much leftover capacity by $d_{i}$ as
${\mathcal{S}}^{*}$. Therefore, in turn $\hat{A}(i,p)$ is at least as much as
the leftover capacity in ${\mathcal{S}}^{*}$. Since we assume
${\mathcal{S}}^{*}$ to have the largest leftover capacity with profit at least
$p$, all the inequalities must be equalities.

∎

Our next result gives the approximation guarantee for Algorithm 9.

######  Lemma 15.

Let $\mathcal{S}^{*}$ be the optimal solution set to the original MPBKP-S, and
$P_{0}$ satisfy (10). Let $\mathcal{S}^{\prime}$ denote the optimal solution
set by Algorithm 9, i.e., $\mathcal{S}^{\prime}$ is the solution set
corresponding to $\hat{A}(n,p^{*})$ where $p^{*}$ is the maximum $p$ such that
$\hat{A}(n,p)>-\infty$. Then,

$\mathcal{P}(\mathcal{S}^{\prime})\geq
p^{*}\geq(1-\epsilon)\mathcal{P}(\mathcal{S}^{*}).$

###### Proof of Lemma 15.

For any item $i$, because of rounding down, $\hat{r}_{i}$ is smaller than
$r_{i}$. Also there are at most $n$ rounding ups on the penalties in
${\mathcal{S}}^{*}$, each by not more than $\kappa$. Then,

$\mathcal{P}({\mathcal{S}}^{*})-\hat{\mathcal{P}}({\mathcal{S}}^{*})\leq
2n\kappa.$

The dynamic programming step must return a set, ${\mathcal{S}}^{\prime}$, at
least as good as ${\mathcal{S}}^{*}$ under the new profit. Therefore,

$\displaystyle\mathcal{P}({\mathcal{S}}^{\prime})$