# Faster Knapsack Algorithms via Bounded Monotone Min-Plus-
Convolution††thanks: This work is part of the project TIPEA that has received
funding from the European Research Council (ERC) under the European Unions
Horizon 2020 research and innovation programme (grant agreement No. 850979).

Karl Bringmann Saarland University and Max Planck Institute for Informatics,
Saarland Informatics Campus, Saarbrücken, Germany. Alejandro
Cassis††footnotemark:

###### Abstract

We present new exact and approximation algorithms for 0-1-Knapsack and
Unbounded Knapsack:

  * $\blacksquare$

_Exact Algorithm for 0-1-Knapsack:_ 0-1-Knapsack has known algorithms running
in time $\widetilde{O}(n+\min\\{n\cdot\mathrm{OPT},n\cdot
W,\mathrm{OPT}^{2},W^{2}\\})$ [Bellman ’57], where $n$ is the number of items,
$W$ is the weight budget, and $\mathrm{OPT}$ is the optimal profit. We present
an algorithm running in time $\widetilde{O}(n+(W+\mathrm{OPT})^{1.5})$. This
improves the running time in case $n,W,\mathrm{OPT}$ are roughly equal.

  * $\blacksquare$

_Exact Algorithm for Unbounded Knapsack:_ Unbounded Knapsack has known
algorithms running in time $\widetilde{O}(n+\min\\{n\cdot p_{\max},n\cdot
w_{\max},p_{\max}^{2},w_{\max}^{2}\\})$ [Axiotis, Tzamos ’19, Jansen,
Rohwedder ’19, Chan, He ’22], where $n$ is the number of items, $w_{\max}$ is
the largest weight of any item, and $p_{\max}$ is the largest profit of any
item. We present an algorithm running in time
$\widetilde{O}(n+(p_{\max}+w_{\max})^{1.5})$, giving a similar improvement as
for 0-1-Knapsack.

  * $\blacksquare$

_Approximating Unbounded Knapsack with Resource Augmentation:_ Unbounded
Knapsack has a known FPTAS with running time
$\widetilde{O}(\min\\{n/\varepsilon,n+1/\varepsilon^{2}\\})$ [Jansen, Kraft
’18]. We study _weak_ approximation algorithms, which approximate the optimal
profit but are allowed to overshoot the weight constraint (i.e. resource
augmentation). We present the first approximation scheme for Unbounded
Knapsack in this setting, achieving running time
$\widetilde{O}(n+1/\varepsilon^{1.5})$. Along the way, we also give a simpler
FPTAS with lower order improvement in the standard setting.

For all of these problem settings the previously known results had matching
conditional lower bounds. We avoid these lower bounds in the approximation
setting by allowing resource augmentation, and in the exact setting by
analyzing the time complexity in terms of weight and profit parameters
(instead of only weight or only profit parameters).

Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone
sequences with bounded entries. These structured instances of Min-Plus-
Convolution can be solved in time $O(n^{1.5})$ [Chi, Duan, Xie, Zhang ’22] (in
contrast to the conjectured $n^{2-o(1)}$ lower bound for the general case). We
complement our results by showing reductions in the opposite direction, that
is, we show that achieving our results with the constant 1.5 replaced by any
constant $<2$ implies subquadratic algorithms for Min-Plus-Convolution on
monotone sequences with bounded entries.

##  Introduction

In this paper we present new exact and approximation algorithms for Knapsack
problems.

##### Exact Pseudopolynomial Algorithms for Unbounded Knapsack

In the Unbounded Knapsack problem we are given a set of $n$ items, where each
item has a weight $w_{i}$ and a profit $p_{i}$, along with a knapsack capacity
$W$. The goal is to find a _multiset_ of items which maximizes the total
profit and has total weight at most $W$. The textbook dynamic programming
algorithm for Unbounded Knapsack due to Bellman [Bel57] runs in time $O(nW)$
or in time $O(n\cdot\mathrm{OPT})$, where $\mathrm{OPT}$ is the value of the
optimal solution. Recent literature on Unbounded Knapsack studies alternative
parameters: Axiotis and Tzamos [AT19] and Jansen and Rohwedder [JR19]
independently presented algorithms running in time
$\widetilde{O}(w_{\max}^{2})$ and $\widetilde{O}(p_{\max}^{2})$,111We use the
notation $\widetilde{O}(T)=\cup_{c>0}O(T\log^{c}T)$ to supress polylogarithmic
factors where $w_{\max}$ is the largest weight of any item and $p_{\max}$ the
largest profit of any item — in general $w_{\max}$ could be much smaller than
$W$ and $p_{\max}$ much smaller than $\mathrm{OPT}$, so these algorithms
improve upon Bellman’s algorithm for some parameter settings. Chan and He
[CH22] presented further improvements222Note that we can assume that $n\leq
w_{\max}$ without loss of generality since if there are multiple items with
the same weight, we can keep only the one with the largest profit. Similarly,
$n\leq p_{\max}$. achieving time $\widetilde{O}(n\,w_{\max})$ and
$\widetilde{O}(n\,p_{\max})$ Note that when $w_{\max}\approx p_{\max}\approx
n$ all mentioned algorithms require at least quadratic time $\Omega(n^{2})$.
Can we overcome this quadratic barrier? In this paper we answer this
positively by considering the combined parameter $w_{\max}+p_{\max}$.

######  Theorem 1.

Unbounded Knapsack can be solved in expected time
$\widetilde{O}(n+(p_{\max}+w_{\max})^{1.5})$.

This result is particularly interesting in light of recent fine-grained lower
bounds for Unbounded Knapsack. Indeed, for each previous result that we have
mentioned above, a matching conditional lower bound is known [CMWW19, KPS17].
For example, Unbounded Knapsack cannot be solved in time $O((n+W)^{2-\delta})$
for any constant $\delta>0$ under a plausible hypothesis. Inspecting these
conditional lower bounds, we observe that they construct hard instances where
only the profit parameters or only the weight parameters are under control;
one of the two must be very large to obtain a hardness reduction. We thus
avoid these conditional lower bounds by considering the combined profit and
weight parameter $w_{\max}+p_{\max}$.

##### Exact Pseudopolynomial Algorithms for 0-1 Knapsack

The 0-1 Knapsack problem is the variant of Unbounded Knapsack where every
input item can appear at most once in any solution. Bellman’s algorithm also
solves 0-1 Knapsack in time $O(nW)$ or $O(n\cdot\mathrm{OPT})$. However, the
landscape is more diverse when considering other parameters. In particular, it
is open whether 0-1 Knapsack can be solved in time
$\widetilde{O}(n+w_{\max}^{2})$ or $\widetilde{O}(n+p_{\max}^{2})$.333This gap
is analogous to the case of Subset Sum where we are given a set of numbers $X$
and a target number $t$. For the unbounded case, where the goal is to find
whether a multiset of items in $X$ sums to $t$, Jansen and Rohwedder [JR19]
gave an algorithm in time $\widetilde{O}(n+u)$ where $u$ is the largest number
in the input. For the more standard “0-1” case where we ask for a subset of
$X$ summing to $t$, the best known running times are $\widetilde{O}(n+t)$
[Bri17, JW19], $O(nu)$ [Pis99], $\widetilde{O}(n+u^{2}/n)$ by combining [GM91]
and [Bri17, JW19], and $\widetilde{O}(n+u^{3/2})$ by combining [GM91] and
[Bri17, JW19] and [Pis99]; see also [BW21, PRW21] for generalizations to $X$
being a multiset and related results. Table 1 shows a non-exhaustive list of
pseudopolynomial-time algorithms for 0-1 Knapsack using different combinations
of the parameters $n,w_{\max},p_{\max},W,\mathrm{OPT}$. Note that when all
these parameters are bounded by $O(n)$, all existing algorithms require at
least quadratic time $\Omega(n^{2})$. In this paper we show that by
considering the combined weight and profit parameter $W+\mathrm{OPT}$ we can
overcome this quadratic barrier.

######  Theorem 2.

There is a randomized algorithm for 0-1 Knapsack that runs in time
$\widetilde{O}(n+(W+\mathrm{OPT})^{1.5})$ and succeeds with high probability.

Similar to the unbounded case, matching conditional lower bounds ruling out
time $O((n+W)^{2-\delta})$ and $O((n+\mathrm{OPT})^{2-\delta})$ for any
$\delta>0$ are known [CMWW19, KPS17]. These lower bounds construct hard
instances where only one of $W,\mathrm{OPT}$ is under control, the other needs
to be very large. We thus avoid these lower bounds by considering the combined
weight and profit parameter $W+\mathrm{OPT}$.

Table 1: Non-exhaustive list of pseudopolynomial-time algorithms for 0-1 Knapsack. Running Time |  Reference
---|---
$O(n\cdot\min\\{W,\mathrm{OPT}\\})$ | [Bel57]
$O(n\cdot p_{\max}\cdot w_{\max})$ | [Pis99]
$\widetilde{O}(n+w_{\max}\cdot W)$ | [KP04, BHSS18, AT19]
$\widetilde{O}(n+p_{\max}\cdot W)$ | [BHSS18]
$\widetilde{O}(n\cdot\min\\{w_{\max}^{2},p_{\max}^{2}\\})$ | [AT19]
$\widetilde{O}((n+W)\cdot\min\\{w_{\max},p_{\max}\\})$ | [BHSS18]
$O(n+\min\\{w_{\max}^{3},p_{\max}^{3}\\})$ | [PRW21]
$\widetilde{O}(n+(W+\mathrm{OPT})^{1.5})$ | Theorem 2

##### Approximation Schemes for Unbounded Knapsack

Since Unbounded Knapsack is well known to be NP-hard, it is natural to study
approximation algorithms. In particular, a _fully polynomial-time
approximation scheme_ (FPTAS) given $0<\varepsilon<1$ computes a solution $x$
with total weight $w(x)\leq W$ and total profit
$p(x)\geq(1-\varepsilon)\mathrm{OPT}$ in time
$\operatorname{poly}(n,1/\varepsilon)$. The first FPTAS for Unbounded Knapsack
was designed by Ibarra and Kim in 1975 [IK75] and runs in time
$\widetilde{O}(n+(1/\varepsilon)^{4})$. In 1979 Lawler [Law79] improved the
running time to $\widetilde{O}(n+(1/\varepsilon)^{3})$. This was the best
known until Jansen and Kraft in 2018 [JK18] presented an FPTAS running in time
$\widetilde{O}(n+(1/\varepsilon)^{2})$. This algorithm has a matching
conditional lower ruling out time $O((n+1/\varepsilon)^{2-\delta})$ for any
$\delta>0$ [CMWW19, KPS17, MWW19].

We present a new FPTAS for Unbounded Knapsack which is (as we believe) simpler
than Jansen and Kraft’s, and has a lower order improvement in the running
time:

######  Theorem 3.

Unbounded Knapsack has an FPTAS with running time
$\widetilde{O}\bigg{(}n+\frac{(1/\varepsilon)^{2}}{2^{\Omega(\sqrt{\log(1/\varepsilon)})}}\bigg{)}$.

Bringmann and Nakos [BN21] recently gave an FPTAS for the related Subset Sum
problem which achieves the same running time.

##### Weak Approximation for Unbounded Knapsack

Motivated by the matching upper and conditional lower bounds for FPTASs for
Unbounded Knapsack, we study the relaxed notion of _weak approximation_ as
coined in [MWW19]: we relax the weight constraint and seek a solution $x$ with
total weight $w(x)\leq(1+\varepsilon)W$ and total profit
$p(x)\geq(1-\varepsilon)\mathrm{OPT}$. Note that $\mathrm{OPT}$ is still the
optimal value of any solution with weight at most $W$. This can be interpreted
as bicriteria approximation (approximating both the weight and profit
constraint) or as resource augmentation (the optimal algorithm is allowed
weight $W$ while our algorithm is allowed a slightly larger weight of
$(1+\varepsilon)W$). All of these are well-established relaxations of the
standard (=strong444From now on, by “strong” approximation we mean the
standard (non-weak) notion of approximation.) notion of approximation. Such
weaker notions of approximation are typically studied when a PTAS for the
strong notion of approximation is not known. More generally, studying these
weaker notions is justified whenever there are certain limits for strong
approximations, to see whether these limits can be overcome by relaxing the
notion of approximation. In particular, we want to understand whether this
relaxation can overcome the conditional lower bound ruling out time
$O((n+1/\varepsilon)^{2-\delta})$. For the related Subset Sum problem this
question has been resolved positively: Bringmann and Nakos [BN21]
conditionally ruled out strong approximation algorithms in time
$O((n+1/\varepsilon)^{2-\delta})$ for any $\delta>0$, but Mucha, Węgrzycki and
Włodarczyk [MWW19] designed a weak FPTAS in time
$\widetilde{O}(n+(1/\varepsilon)^{5/3})$.

In this paper, we give a positive answer for Unbounded Knapsack:

######  Theorem 4.

Unbounded Knapsack has a weak approximation scheme running in expected time
$\widetilde{O}(n+(\tfrac{1}{\varepsilon})^{1.5})$.

Our theorem gives reason to believe that resource augmentation indeed makes
the problem easier. Specifically, obtaining a strong approximation scheme with
the same running time as our weak one would refute the existing conditional
lower bound for strong approximation.

##### Min-Plus-Convolution

All conditional lower bounds mentioned above are based on a hypothesis about
the MinConv problem: Given sequences $A,B\in\mathbb{Z}^{n}$ compute their
$(\min,+)$-convolution, which is the sequence $C\in\mathbb{Z}^{2n}$ with
$C[k]=\min_{i+j=k}A[i]+B[j]$.555If we replace the $\min$ by a $\max$, we
obtain the MaxConv problem, which is equivalent to MinConv after negating the
sequences. Therefore, we will sometimes use these two names interchangeably.
The MinConv problem can be trivially solved in time $O(n^{2})$. This can be
improved to time $n^{2}/2^{\Omega(\sqrt{\log n})}$ via a reduction to
$(\min,+)$-matrix product due to Bremner et al. [BCD+14], and using Williams’
algorithm for the latter [Wil18] (which was derandomized later by Chan and
Williams [CW21]). The lack of truly subquadratic algorithms despite
considerable effort has led researchers to postulate the MinConv hypothesis,
namely that MinConv cannot be solved in time $O(n^{2-\delta})$ for any
constant $\delta>0$ [CMWW19, KPS17]. Many problems are known to have
conditional lower bounds from the MinConv hypothesis, see, e.g., [BIS17, CH19,
CMWW19, JR19, KPS17, LRC14].

Central to our work is a reduction from MinConv to Unbounded Knapsack shown
independently by Cygan et al. [CMWW19] and Künnemann et al. [KPS17]. In
particular, they showed that if Unbounded Knapsack on $n$ items and $W=O(n)$
can be solved in subquadratic time, then MinConv can be solved in subquadratic
time. This reduction immediately implies matching conditional lower bounds for
the previously known exact algorithms with running times $O(nW)$,
$\widetilde{O}(w_{\max}^{2})$ and $\widetilde{O}(n\,w_{\max})$, as mentioned
earlier.

A small modification of this reduction extends to the dual case, i.e., an
exact subquadratic-time algorithm for Unbounded Knapsack with
$\mathrm{OPT}=O(n)$ would result in a subquadratic-time algorithm for MinConv.
This establishes matching conditional lower bounds for the algorithms in time
$O(n\cdot\mathrm{OPT})$, $\widetilde{O}(p_{\max}^{2})$ and
$\widetilde{O}(n\,p_{\max})$. Moreover, by setting
$\varepsilon=\Theta(1/\mathrm{OPT})$, an FPTAS for Unbounded Knapsack would
yield an exact algorithm for MinConv, establishing that the
$\widetilde{O}(n+(1/\varepsilon)^{2})$-time FPTAS is conditionally optimal.
This last observation was pointed out in [MWW19].

In fact, the reduction due to Cygan et al. [CMWW19] is even an equivalence,
showing that Unbounded Knapsack is intimately connected to MinConv. The same
reduction is also known for 0-1 Knapsack [CMWW19, KPS17], so a similar
discussion applies to 0-1 Knapsack.

##### Bounded Monotone Min-Plus-Convolution

Despite its postulated hardness, there are restricted families of instances of
MinConv for which subquadratic algorithms are known, see e.g. [BGSW19, BHWZ94,
CL15, CDXZ22]. Central to this paper is the case when the input sequences
$A,B\in\mathbb{Z}^{n}$ are monotone non-decreasing and have entries bounded by
$O(n)$; we call this task BMMinConv.

In a celebrated result, Chan and Lewenstein gave an algorithm for BMMinConv
that runs in expected time $O(n^{1.859})$ [CL15]. As a big hammer, their
algorithm uses the famous Balog-Szemerédi-Gowers theorem from additive
combinatorics. Very recently, Chi, Duan, Xie and Zhang showed how to avoid
this big hammer and improved the running time to expected
$\widetilde{O}(n^{1.5})$ [CDXZ22].

All of our results mentioned so far use this BMMinConv algorithm as a
subroutine. That is, our algorithms are reductions from various Knapsack
problems to BMMinConv.

##### Equivalence with Bounded Monotone Min-Plus-Convolution

We complement our results by showing reductions in the opposite direction:
Following the same chain of reductions as in [CMWW19, KPS17] but starting from
bounded monotone instances of $(\min,+)$-convolution, we reduce BMMinConv to
$O(n)$ instances of Unbounded Knapsack with $O(\sqrt{n})$ items each, where it
holds that $w_{\max},p_{\max},W$ and $\mathrm{OPT}$ are all bounded by
$O(\sqrt{n})$. Instantiating this reduction for the exact and approximate
setting, we show the following theorem.

######  Theorem 5 (Equivalence).

For any problems $A$ and $B$ from the following list, if $A$ can be solved in
time $\widetilde{O}(n^{2-\delta})$ for some $\delta>0$, then $B$ can be solved
in randomized time $\widetilde{O}(n^{2-\delta/2})$:

  1. 1.

BMMaxConv on sequences of length $n$

  2. 2.

Unbounded Knapsack on $n$ items and $W,\mathrm{OPT}=O(n)$

  3. 3.

0-1 Knapsack on $n$ items and $W,\mathrm{OPT}=O(n)$

  4. 4.

Weak $(1+\varepsilon)$-approximation for Unbounded Knapsack on $n$ items and
$\varepsilon=\Theta(1/n)$

On the one hand, Theorem 1 solves Unbounded Knapsack in time
$\widetilde{O}(n+(p_{\max}+w_{\max})^{1.5})$ by using Chi, Duan, Xie and
Zhang’s subquadratic BMMinConv algorithm [CDXZ22]. On the other hand, Theorem
5 shows that any algorithm solving Unbounded Knapsack in time
$\widetilde{O}(n+(p_{\max}+w_{\max})^{2-\delta})$ can be transformed into a
subquadratic BMMinConv algorithm. This shows that both our exact and
approximation algorithms take essentially _the only possible route_ to obtain
subquadratic algorithms, by invoking a BMMinConv algorithm.

##### Is randomness necessary?

The algorithms given by Theorems 1, 2 and 4 are all randomized. If we insist
on deterministic algorithms, we note that by applying Chan and Lewenstein’s
deterministic $\widetilde{O}(n^{1.864})$-time algorithm for BMMaxConv [CL15],
we can obtain deterministic versions of Theorem 1 and Theorem 4 with exponent
$1.864$ instead of $1.5$ (i.e. the only part where we use randomness is in
applying Chi, Duan, Xie and Zhang’s algorithm [CDXZ22]). On the other hand, we
do not know666Our algorithm closely follows Bringmann’s algorithm for Subset
Sum [Bri17] whose derandomization is an open problem. how to derandomize
Theorem 2.

###  Technical Overview

##### Exact algorithm for Unbounded Knapsack

In Section 3 we present our exact algorithm for Unbounded Knapsack. Let
$(\mathcal{I},W)$ be an instance of Unbounded Knapsack. We denote by
$\mathcal{P}_{i}[0,\dots,W]$ the array where $\mathcal{P}_{i}[j]$ is the
maximum profit of a solution of weight at most $j$ using at most $2^{i}$
items. Since each item has weight at least 1, any feasible solution consists
of at most $W$ items. Thus, our goal is to compute the value
$\mathcal{P}_{\lceil\log W\rceil}[W]=\mathrm{OPT}$.

The natural approach is to use dynamic programming: since $\mathcal{P}_{0}$
consists of solutions of at most one item, it can be computed in time $O(n)$.
For $i>0$ we can compute $\mathcal{P}_{i}[0,\dots,W]$ by taking the
$(\max,+)$-convolution of $\mathcal{P}_{i-1}[0,\dots,W]$ with itself. This
gives an algorithm in time $O(W^{2}\log W)$.

Jansen and Rohwedder [JR19] and Axiotis and Tzamos [AT19] showed that instead
of convolving sequences of length $W$, it suffices to convolve only
$O(w_{\max})$ entries of $\mathcal{P}_{i-1}$ in each iteration. This improves
the running time to $O(w_{\max}^{2}\log W)$ by using the naive algorithm for
$(\max,+)$-convolution. The approach of Jansen and Rohwedder [JR19] is as
follows. Suppose $x$ is the optimal solution for a target value
$\mathcal{P}_{i}[j]$. They showed that $x$ can be split into two solutions
$x_{1},x_{2}$ such that (i) the number of items in each part is at most
$2^{i-1}$ and (ii) the difference between the weights of both parts is at most
$O(w_{\max})$. Thus, (i) guarantees that both $x_{1}$ and $x_{2}$ are optimal
solutions for two entries of $\mathcal{P}_{i-1}$, and (ii) implies that these
entries lie in an interval in $\mathcal{P}_{i-1}$ of length $O(w_{\max})$. In
this way, they can afford to perform the $(\max,+)$-convolution of only
$O(w_{\max})$ entries in $\mathcal{P}_{i-1}$.

To show the existence of such a partitioning of $x$ they make use of Steinitz’
Lemma [Ste13], which shows that any collection of $m$ vectors in
$\mathbb{R}^{d}$ with infinity norm at most 1, whose sum is 0, can be permuted
such that every prefix sum has norm at most $O(d)$ (see Lemma 11 for the
precise statement). The partitioning of $x$ follows from Steinitz’ Lemma by
taking the weights of the items picked by $x$ as 1-dimensional vectors. The
usage of Steinitz’ Lemma to reduce the number of states in dynamic programs
was pioneered by Eisenbrand and Weismantel [EW20], and further refined by
Jansen and Rohwedder [JR19].

In our algorithm, we use Steinitz’ Lemma in a similar way to split the number
of items and the weight of $x$, but additionally we use it to ensure that the
profits of the solutions $x_{1},x_{2}$ differ by at most $O(p_{\max})$ (see
Lemma 12). In this way, by carefully handling the subproblems
$\mathcal{P}_{i-1}$ we can enforce that the values of the $O(w_{\max})$
entries that need to be convolved have values in a range of size
$O(p_{\max})$. Since the arrays $\mathcal{P}_{i}$ are monotone non-decreasing,
we can then apply the algorithm for BMMaxConv, and thus handle each subproblem
in time $\widetilde{O}((p_{\max}+w_{\max})^{1.5})$.

##### Exact algorithm for 0-1 Knapsack

Cygan et al. [CMWW19] showed that there is a reduction from 0-1 Knapsack to
MaxConv. More precisely, they showed that if MaxConv can be solved in time
$T(n)$, then 0-1 Knapsack can be solved in randomized time
$\widetilde{O}(T(W))$. Their reduction is a generalization of Bringmann’s
Subset Sum algorithm [Bri17], which can be seen as a reduction from Subset Sum
to Boolean convolution. Cygan et al. showed that the reduction for 0-1
Knapsack can be obtained by essentially replacing the Boolean convolutions by
$(\max,+)$-convolutions in Bringmann’s algorithm.

In Section 4 we observe that this reduction produces instances of MaxConv
which are monotone non-decreasing and have entries bounded by $\mathrm{OPT}$.
That is, we obtain BMMaxConv instances of size $O(W+\mathrm{OPT})$, and
following the analysis of [CMWW19] we obtain an algorithm for 0-1 Knapsack in
time $\widetilde{O}(n+(W+\mathrm{OPT})^{1.5})$, which yields Theorem 2.

##### Approximating Unbounded Knapsack

In Section 5 we present our approximation schemes for Unbounded Knapsack. Let
$(\mathcal{I},W)$ be an instance of Unbounded Knapsack. The starting point is
the “repeated squaring” approach mentioned earlier. Namely, recall that we
denote by $\mathcal{P}_{i}[0,\dots,W]$ the sequence where $\mathcal{P}_{i}[j]$
is the maximum profit of any solution of weight at most $j$ and with at most
$2^{i}$ items. Since $W/w_{\min}$ is an upper bound on the number of items in
the optimal solution, we have that
$\mathcal{P}_{\log(W/w_{\min})}[W]=\mathrm{OPT}$. We can compute
$\mathcal{P}_{i}[0,\dots,W]$ by taking the $(\max,+)$-convolution of
$\mathcal{P}_{i-1}[0,\dots,W]$ with itself. This yields an algorithm in time
$O(W^{2}\log W/w_{\min})$.

Although this exact algorithm is not particularly exciting or new, it can be
nicely extended to the approximate setting. In Section 5.2 we show that by
replacing the exact $(\max,+)$-convolutions with approximate ones, we obtain
an FPTAS for Unbounded Knapsack in time $\widetilde{O}(n+1/\varepsilon^{2})$.
To this end, we preprocess the item set to get rid of _light_ items with
weight smaller than $\varepsilon\cdot W$, and _cheap_ items with profit
smaller than $\varepsilon\cdot\mathrm{OPT}$, while decreasing the optimal
value by only $O(\varepsilon\cdot\mathrm{OPT})$ (see Lemma 23). After this
preprocessing, we have that the maximum number of items in any solution is
$W/w_{\min}<1/\varepsilon$. Thus, we only need to approximate $O(\log
1/\varepsilon)$ convolutions. For this we use an algorithm due to Chan
[Cha18], which in our setting without cheap items runs in time
$\widetilde{O}(1/\varepsilon^{2})$ (see Lemma 24). Thus, after applying the
preprocessing in time $O(n)$, we compute a $(1+\varepsilon)$-approximation of
$\mathcal{P}[0,\dots,W]$ by applying $O(\log 1/\varepsilon)$ approximate
$(\max,+)$-convolutions in overall time
$\widetilde{O}(n+(1/\varepsilon)^{2})$.

In Section 5.3 we treat the case of weak approximation. The main steps of the
algorithm are virtually the same as before. The crucial difference is that now
we can afford to round weights. In this way, we can adapt Chan’s algorithm and
construct MaxConv instances which are monotone non-decreasing and have bounded
entries (see Lemma 28). This yields BMMaxConv instances, and by using Chi,
Duan, Xie and Zhang’s algorithm for this special case [CDXZ22], we can compute
a weak approximation of $(\max,+)$-convolution in time
$\widetilde{O}((1/\varepsilon)^{1.5})$. By similar arguments as for the strong
approximation, this yields a weak approximation scheme running in time
$\widetilde{O}(n+(1/\varepsilon)^{1.5})$.

##### Equivalence between BMMinConv and Knapsack problems

As mentioned earlier in the introduction, Cygan et al. [CMWW19] and Künnemann
et al. [KPS17] independently showed a reduction from MinConv to Unbounded
Knapsack. In Section 6 we show that following the same chain of reductions
from MaxConv to Unbounded Knapsack but instead starting from BMMaxConv, with
minor adaptations we can produce instances of Unbounded Knapsack with
$W,\mathrm{OPT}=O(n)$. Together with our exact algorithm for Unbounded
Knapsack, which we can phrase as a reduction to BMMaxConv, we obtain an
equivalence of BMMaxConv and Unbounded Knapsack with $W,\mathrm{OPT}=O(n)$ —
if one of these problems can be solved in subquadratic time, then both can.

Note that for Unbounded Knapsack with $W,\mathrm{OPT}=O(n)$ a weak
$(1+\varepsilon)$-approximation for $\varepsilon=\Theta(1/n)$ already computes
an exact optimal solution. This yields the reduction from BMMaxConv to the
approximate version of Unbounded Knapsack. We similarly obtain a reduction to
0-1 Knapsack with $W,\mathrm{OPT}=O(n)$. This yields our equivalences from
Theorem 5.

##  Preliminaries

We write $\mathbb{N}=\\{0,1,2,\dots\\}$. For $t\in\mathbb{N}$ we let
$[t]=\\{0,1,\dots,t\\}$. For reals $a\leq b$ we write $[a,b]$ for the interval
from $a$ to $b$, and for reals $a,b$ with $b\geq 0$ we write $[a\pm b]$ for
the interval $[a-b,a+b]$.

We formally define the Unbounded Knapsack problem. We are given a set of items
$\mathcal{I}=\\{(p_{1},w_{1}),\dots,(p_{n},w_{n})\\}$, where each item $i$ has
a profit $p_{i}\in\mathbb{N}$ and a weight $w_{i}\in\mathbb{N}$, and a
knapsack capacity $W\in\mathbb{N}$. The task is to maximize
$\sum_{i=1}^{n}p_{i}\cdot x_{i}$ subject to the constraints
$\sum_{i=1}^{n}w_{i}\cdot x_{i}\leq W$ and $x\in\mathbb{N}^{n}$. The more
standard 0-1 Knapsack problem is defined in the same way, but the solution $x$
is constrained to $x\in\\{0,1\\}^{n}$.

Given an instance $(\mathcal{I},W)$, we denote by $x\in\mathbb{N}^{n}$ a
multiset of items, where $x_{i}$ is the number of copies of the $i$-th item.
We sometimes refer to $x$ as a _solution_. We write $p_{\mathcal{I}}(x)$ for
the total profit of $x$, i.e., $p_{\mathcal{I}}(x):=\sum_{i}x_{i}\cdot p_{i}$.
Similarly, we write $w_{\mathcal{I}}(x):=\sum_{i}x_{i}\cdot w_{i}$ for the
weight of $x$. When the item set $\mathcal{I}$ is clear from context, we drop
the subscript and simply write $p(x)$ and $w(x)$. We denote the number of
items contained in a solution $x$ by $\|x\|_{1}:=\sum_{i}x_{i}$. A solution
$x$ is _feasible_ if it satisfies the constraint $w(x)\leq W$. We denote by
$\mathrm{OPT}$ the maximum profit $p(x)$ of any feasible solution $x$. We
denote by $p_{\max}:=\max_{(p,w)\in\mathcal{I}}p$ the maximum profit of any
input item and by $w_{\max}:=\max_{(p,w)\in\mathcal{I}}w$ the maximum weight
of any input item.

##### Notions of Approximation

We say that an algorithm gives a _strong_ $(1+\varepsilon)$-approximation for
Unbounded Knapsack if it returns a solution $x\in\mathbb{N}^{n}$ with weight
$w(x)\leq W$ and profit $p(x)\geq(1-\varepsilon)\cdot\mathrm{OPT}$. We say
that an algorithm gives a _weak_ $(1+\varepsilon)$-approximation for Unbounded
Knapsack if it returns a solution $x\in\mathbb{N}^{n}$ with profit
$p(x)\geq(1-\varepsilon)\cdot\mathrm{OPT}$ and weight
$w(x)\leq(1+\varepsilon)\cdot W$. We stress that here $\mathrm{OPT}$ still
denotes the optimum value with weight at most $W$, i.e.,
$\mathrm{OPT}=\max\\{p(x)\mid x\in\mathbb{N}^{n},\,w(x)\leq W\\}$.

##### Profit Sequences

Given an item set $\mathcal{I}$ and capacity $W$, we define the array
$\mathcal{P}_{\mathcal{I}}[0,\dots,W]$, where $\mathcal{P}_{\mathcal{I}}[j]$
is the maximum profit achievable with capacity $j$, i.e.,

$\mathcal{P}_{\mathcal{I}}[j]:=\max\\{p_{\mathcal{I}}(x)\colon
x\in\mathbb{N}^{n},w_{\mathcal{I}}(x)\leq j\\}.$

Note that $\mathcal{P}_{\mathcal{I}}[0]=0$. A textbook way to compute
$\mathcal{P}_{\mathcal{I}}[0,\dots,W]$ is by dynamic programming:

######  Fact 6.

$\mathcal{P}_{\mathcal{I}}[0,\dots,W]$ can be computed using dynamic
programming in time $O(n\cdot W)$.

We will also consider the array $\mathcal{P}_{\mathcal{I},k}[0,\dots,W]$,
where we restrict to solutions with at most $2^{k}$ items, for any non-
negative integer $k$, i.e., for any $j\in[W]$ we set

$\mathcal{P}_{\mathcal{I},k}[j]:=\max\\{p_{\mathcal{I}}(x)\colon
x\in\mathbb{N}^{n},w(x)\leq j,\|x\|_{1}\leq 2^{k}\\}.$

When $\mathcal{I}$ is clear from context, we will drop the subscript and write
$\mathcal{P}[0,\dots,W]$ and $\mathcal{P}_{k}[0,\dots,W]$. When we work with
0-1 Knapsack instead of Unbounded Knapsack, we will use the same notation
$\mathcal{P}_{\mathcal{I}}$ and $\mathcal{P}_{\mathcal{I},k}$, where we
restrict to $x\in\\{0,1\\}^{n}$ instead of $x\in\mathbb{N}^{n}$.

##### MaxConv

The $(\max,+)$-convolution $A\oplus B$ of two sequences
$A[0,\dots,n],B[0,\dots,n]\in\mathbb{Z}^{n+1}$ is a sequence of length $2n+1$
where $(A\oplus B)[k]:=\max_{i+j=k}A[i]+B[j]$. We call MaxConv the task of
computing the $(\max,+)$-convolution of two given sequences.

We will use the following handy notation: Given sequences
$A[0,\dots,n],B[0,\dots,n]$ and intervals $I,J\subseteq[n]$ and
$K\subseteq[2n]$, we denote by $C[K]:=A[I]\oplus B[J]$ the computation of
$C[k]:=\max\\{A[i]+B[j]\colon i\in I,j\in J,i+j=k\\}$ for each $k\in K$. The
following proposition shows that this can be computed efficiently. We defer
the proof to Appendix A.

######  Proposition 7.

If MaxConv can be solved in time $T(n)$, then $C[K]=A[I]\oplus B[J]$ can be
computed in time $O(T(|I|+|J|)+|K|)$.

Sometimes we will refer to the $(\min,+)$-convolution, where we replace $\max$
by a $\min$. The two problems MinConv and MaxConv are equivalent after
negating the sequences.

##### BMMaxConv

In the BMMaxConv problem, we compute the $(\max,+)$-convolution of sequences
of length $n$ which are monotone non-decreasing and have bounded values. For
this setting, Chi, Duan, Xie and Zhang gave the following remarkable result:

######  Theorem 8 (BMMaxConv [CDXZ22]).

Given monotone non-decreasing sequences $A[0,\dots,n]$ and $B[0,\dots,n]$ with
entries $A[i],B[i]\in[O(n)]\cup\\{-\infty\\}$ for all $i\in[n]$, their
$(\max,+)$-convolution $A\oplus B$ can be computed in expected time
$\widetilde{O}(n^{1.5})$.

Note that Chi, Duan, Xie and Zhang phrase their result for
$(\min,+)$-convolution of increasing sequences with entries in $[O(n)]$. We
prove in Appendix A that both statements are equivalent, so their result also
works for $(\max,+)$-convolution with entries in $[O(n)]\cup\\{-\infty\\}$.

##### Witnesses

Let $A[0,\dots,n],B[0,\dots,n]$ be an instance of BMMaxConv. Let $C:=A\oplus
B$. Given $k\in[2n]$, we say that $i\in[n]$ is a _witness_ for $C[k]$ if
$C[k]=A[i]+B[k-i]$. We say that an array $M[0.\dots,2n]$ is a _witness array_
, if each entry $M[k]$ contains some witness for $C[k]$.

For the general case of MaxConv it is well known (e.g. [Sei95, AGMN92]) that
computing the witness array has the same time complexity as
$(\max,+)$-convolution, up to a $\operatorname{polylog}(n)$ overhead. This
reduction does not immediately apply to BMMaxConv because the sequences might
not remain monotone. However, we make it work with some extra care, see
Appendix B for the proof.

######  Lemma 9 (Witness Finding).

If BMMaxConv can be computed in time $T(n)$, then a witness array
$M[0,\dots,2n]$ can be computed in time $\widetilde{O}(T(n))$.

##### Niceness asumptions on time bounds

For all time bounds $T(n)$ in this paper, we make the following niceness
assumptions: (1) $T(\widetilde{O}(n))\leq\widetilde{O}(T(n))$, and (2) $k\cdot
T(n)\leq O(T(kn))$ for any $k,n\geq 1$. This is satisfied for all natural time
bounds of polynomial-time or pseudopolynomial-time algorithms, in particular
it holds for all functions of the form $T(n)=\Theta(n^{\alpha}\log^{\beta}n)$
for any constants $\alpha\geq 1,\beta\geq 0$.

##  Exact algorithm for Unbounded Knapsack

In this section we prove the following Theorem:

######  Theorem 10.

If BMMaxConv on length-$n$ sequences can be solved in time $T(n)$, then
Unbounded Knapsack can be solved in time
$\widetilde{O}(n+T(p_{\max}+w_{\max}))$, where $p_{\max}$ is the largest
profit of any item and $w_{\max}$ is the largest weight of any item.

Note that Theorem 1 follows as an immediate corollary of Theorem 10 by
plugging in Chi, Duan, Xie and Zhang’s algorithm (Theorem 8).

For the entire section, fix an instance $(\mathcal{I},W)$ of the Unbounded
Knapsack problem. Recall that $\mathcal{P}_{i}[0,\dots,W]$ is defined as
$\mathcal{P}_{i}[j]:=\max\\{p(x)\colon w(x)\leq j,\|x\|_{1}\leq 2^{i}\\}$, and
set $\Delta:=p_{\max}+w_{\max}$. Suppose we know that the optimal solution
consists of at most $2^{k}$ items. Then, our goal is to compute the value
$\mathcal{P}_{k}[W]$. The natural approach is to use dynamic programming: if
we have computed $\mathcal{P}_{i-1}$, then
$\mathcal{P}_{i}=\mathcal{P}_{i-1}\oplus\mathcal{P}_{i-1}$. To get our desired
running time, we will show that we only need to convolve $O(\Delta)$ entries
of $\mathcal{P}_{i-1}$ and that we can enforce that all of these fall in a
range of $O(\Delta)$ values. By monotonicity of $\mathcal{P}_{i-1}$, we end up
with a BMMaxConv instance, which can be solved in time $O(T(\Delta))$. The
resulting total time to compute $\mathcal{P}_{i}[W]$ is $O(n+k\cdot
T(\Delta))$. With additional preprocessing we ensure that $k=O(\log\Delta)$,
turning the running time into $\widetilde{O}(n+T(\Delta))$.

###  Preparations

We need to show that when computing the optimal answer for some entry
$\mathcal{P}_{i}[j]$, we can split it in such a way that both its total profit
and its total weight are roughly halved. Our main tool to show this is the
Steinitz Lemma [GS80, Ste13]. A beautiful proof for it can be found in
[Mat10].

######  Lemma 11 ([GS80, Ste13, Steinitz Lemma]).

Let $\|.\|$ be a norm in $\mathbb{R}^{m}$ and let $M$ be an arbitrary
collection of $t$ vectors in $\mathbb{R}^{m}$ such that $\|v\|\leq 1$ for
every $v\in M$ and $\sum_{v\in M}v=0$. Then, it is possible to permute the
vectors in $M$ into a sequence $(v_{1},\dots,v_{t})$ such that
$\|v_{1}+\dots+v_{k}\|\leq m$ holds for every $k\in[t]$.

We use the Steinitz Lemma to argue that the items in a solution can be split
in two parts in such a way that both the total profit and the total weight are
roughly halved:

######  Lemma 12 (Splitting Lemma).

Let $i\geq 1$ and consider a solution $x\in\mathbb{N}^{n}$ with $\|x\|_{1}\leq
2^{i}$. Then there is a partition of $x$ into two solutions
$x_{1},x_{2}\in\mathbb{N}^{n}$ with the following properties:

  1. 1.

(Splitting of Items) $\|x_{1}\|_{1},\|x_{2}\|_{1}\leq 2^{i-1}$ and
$x=x_{1}+x_{2}$,

  2. 2.

(Approximate Splitting of Weight) $|w(x_{1})-\tfrac{1}{2}w(x)|\leq 2\Delta$
and $|w(x_{2})-\tfrac{1}{2}w(x)|\leq 2\Delta$,

  3. 3.

(Approximate Splitting of Value) $|p(x_{1})-\tfrac{1}{2}p(x)]|\leq 2\Delta$
and $|p(x_{2})-\tfrac{1}{2}p(x)]|\leq 2\Delta$.

  * Proof.

Let $t:=\|x\|_{1}\leq 2^{i}$. First assume that $t$ is even; we will remove
this assumption later. Write $x=\sum_{j=1}^{t}x^{(j)}$ where each $x^{(j)}$
corresponds to one copy of some item, i.e. $\|x^{(j)}\|_{1}=1$, and set
$v^{(j)}=\left(\begin{smallmatrix}w(x^{(j)})\\\
p(x^{(j)})\end{smallmatrix}\right)$. Note that
$\|v^{(j)}\|_{\infty}\leq\Delta$. By applying the Steinitz Lemma on the
vectors $v^{(j)}-\tfrac{1}{t}\left(\begin{smallmatrix}w(x)\\\
p(x)\end{smallmatrix}\right)$ (after normalizing by $\Delta$), we can assume
that the $v^{(j)}$’s are ordered such that

$\bigg{\|}\sum_{j=1}^{t/2}v^{(j)}-\frac{1}{2}\begin{pmatrix}w(x)\\\
p(x)\end{pmatrix}\bigg{\|}_{\infty}\leq 2\Delta.$ (1)

Fix this ordering, and let $x_{1}=x^{(1)}+\ldots+x^{(t/2)}$, corresponding to
$v^{(1)},\dots,v^{(t/2)}$, and let $x_{2}=x^{(t/2+1)}+\ldots+x^{(t)}$,
corresponding to the remaining vectors $v^{(t/2+1)},\dots,v^{(t)}$. We now
check that $x_{1},x_{2}$ satisfy the properties of the lemma:

    * $\blacksquare$

Property 1 is clearly satisfied by construction.

    * $\blacksquare$

For property 2, note that (1) implies $|w(x_{1})-\tfrac{1}{2}w(x)|\leq
2\Delta$. Since $w(x_{2})=w(x)-w(x_{1})$, we have that
$|w(x_{2})-\tfrac{1}{2}w(x)|=|\tfrac{1}{2}w(x)-w(x_{1})|\leq 2\Delta$.

    * $\blacksquare$

Property 3 follows in the same way as property 2.

If $t$ is odd, then $t+1\leq 2^{i}$, so we can add a dummy vector
$x^{(t+1)}=0$ with corresponding $v^{(t+1)}:=\left(\begin{smallmatrix}0\\\
0\end{smallmatrix}\right)$ and repeat the same argument with $t:=t+1$. ∎

When we apply Lemma 12 to an optimal solution corresponding to an entry of the
array $\mathcal{P}_{i}$, we obtain the following lemma.

######  Lemma 13.

Let $\beta>0$. For any index $j\in[\beta\pm 8\Delta]\cap[W]$ there are indices
$j_{1},j_{2}\in[\tfrac{\beta}{2}\pm 8\Delta]\cap[W]$ with the following
properties:

  * (i)

$j_{1}+j_{2}=j$,

  * (ii)

$\mathcal{P}_{i}[j]=\mathcal{P}_{i-1}[j_{1}]+\mathcal{P}_{i-1}[j_{2}]$,

  * (iii)

$|\mathcal{P}_{i-1}[j_{1}]-\tfrac{1}{2}\mathcal{P}_{i}[j]|\leq 2\Delta$ and
$|\mathcal{P}_{i-1}[j_{2}]-\tfrac{1}{2}\mathcal{P}_{i}[j]|\leq 2\Delta$.

  * Proof.

Let $x\in\mathbb{N}^{n}$ be an optimal solution for $\mathcal{P}_{i}[j]$, that
is, we have $p(x)=\mathcal{P}_{i}[j]$, $w(x)\leq j$, and $\|x\|_{1}\leq
2^{i}$. We apply Lemma 12 to $x$ and obtain $x_{1},x_{2}\in\mathbb{N}^{n}$
such that $x_{1}+x_{2}=x$. We do a case distinction based on
$w(x_{1}),w(x_{2})$:

    * $\blacksquare$

$w(x_{1}),w(x_{2})\in[\tfrac{j}{2}\pm 4\Delta]$: Let $j_{1}:=w(x_{1})$ and
$j_{2}:=j-j_{1}$; note that $j_{1},j_{2}\in[\tfrac{j}{2}\pm
4\Delta]\subseteq[\tfrac{\beta}{2}\pm 8\Delta]$. We argue that
$p(x_{1})=\mathcal{P}_{i-1}[j_{1}]$ and $p(x_{2})=\mathcal{P}_{i-1}[j_{2}]$.
Indeed, since $w(x_{1})=j_{1}$ the solution $x_{1}$ is feasible for weight
$j_{1}$, so $p(x_{1})\leq\mathcal{P}_{i-1}[j_{1}]$. Similarly, since
$w(x_{2})=w(x)-w(x_{1})\leq j-w(x_{1})=j_{2}$ the solution $x_{2}$ is feasible
for weight $j_{2}$, so $p(x_{2})\leq\mathcal{P}_{i-1}[j_{2}]$. Moreover, by
optimality of $x$ we have
$p(x_{1})+p(x_{2})=p(x)=\mathcal{P}_{i}[j]\geq\mathcal{P}_{i-1}[j_{1}]+\mathcal{P}_{i-1}[j_{2}]$,
so we obtain $p(x_{1})=\mathcal{P}_{i-1}[j_{1}]$ and
$p(x_{2})=\mathcal{P}_{i-1}[j_{2}]$. Using these equations together with
$p(x)=\mathcal{P}_{i}[j]$, property (ii) follows from
$p(x)=p(x_{1})+p(x_{2})$, property (iii) follows from Property 3 of Lemma 12,
and property (i) holds by definition of $j_{2}$.

    * $\blacksquare$

$w(x_{1})<\tfrac{j}{2}-4\Delta$: Property 2 of Lemma 12 implies that
$|w(x_{1})-w(x_{2})|\leq 4\Delta$, and thus $w(x_{2})\leq\tfrac{j}{2}$.
Therefore, $x_{1}$ and $x_{2}$ are feasible for weights
$j_{1}:=\lfloor\tfrac{j}{2}\rfloor$ and $j_{2}:=\lceil\tfrac{j}{2}\rceil$,
respectively. Note that
$j_{1},j_{2}\in[\tfrac{\beta}{2}\pm(4\Delta+1)]\subseteq[\tfrac{\beta}{2}\pm
8\Delta]$. Property (i) is obvious, and properties (ii) and (iii) now follow
as in the first case.

    * $\blacksquare$

$w(x_{1})>\tfrac{j}{2}+4\Delta$: Similarly as the previous case, property 2 of
Lemma 12 implies that $w(x_{2})\geq\tfrac{j}{2}$. Therefore, we have
$w(x)=w(x_{1})+w(x_{2})>j+4\Delta$, which contradicts the assumption $w(x)\leq
j$.

    * $\blacksquare$

$w(x_{2})<\tfrac{j}{2}-4\Delta$ or $w(x_{2})>\tfrac{j}{2}+4\Delta$: Symmetric
to the previous two cases.∎

###  The algorithm

We are now ready to present our algorithm. The idea is to use the Splitting
Lemma 12 to convolve smaller sequences which are bounded and monotone.

Let $\mathcal{I}=\\{(w_{i},p_{i})\\}_{i=1}^{n}$ with capacity constraint $W$
be an instance of Unbounded Knapsack. Since any item has $w_{i}\geq 1$, we
know that any solution $x\in\mathbb{N}^{n}$ consists of at most $W$ items.
Thus, to compute the value of the optimal solution it suffices to compute
$\mathcal{P}_{k}[W]$ where $k:=\lceil\log W\rceil$.

Our approach is as follows. We do binary search for $\mathrm{OPT}$ in the
range $[p_{\max}\cdot W]$. Suppose we have the current guess $\alpha$. Instead
of computing the arrays $\mathcal{P}_{i}$, we compute _clipped versions_ ,
i.e., $C_{i}$ which has the property that $C_{i}[j]\geq\alpha$ if and only if
$\mathcal{P}_{i}[j]\geq\alpha$.

We compute $C_{i}$ as follows: At every step, we only compute the values for
$O(\Delta)$ weights $C_{i}[W\cdot 2^{i-k}\pm 8\Delta]$. For the base case
$i=0$, we simply set
$C_{0}[0,\dots,8\Delta]:=\mathcal{P}_{0}[0,\dots,8\Delta]$. Note that this can
be done in time $O(n+\Delta)$ by doing one pass over the item set, since
$\mathcal{P}_{0}$ only considers solutions with at most one item. Moreover,
observe that $C_{0}[0,\dots,8\Delta]$ is monotone non-decreasing by definition
of $\mathcal{P}_{0}$.

For the general case $i>0$ we first compute an array $A_{i}[W\cdot 2^{i-k}\pm
8\Delta]$ by taking the $(\max,+)$-convolution of $C_{i-1}[W\cdot 2^{i-1-k}\pm
8\Delta]$ with itself. To obtain $C_{i}[W\cdot 2^{i-k}\pm 8\Delta]$, we clip
the values in $A_{i}$ which are too large, and set to $-\infty$ the values
which are to small. This ensures that all values in $C_{i}$ lie within a range
of $O(\Delta)$, except for values that are $-\infty$. Algorithm 1 contains the
pseudocode.

Algorithm 1 Given an instance $(\mathcal{I},W)$ of Unbounded Knapsack and a
guess $\alpha\in[p_{\max}\cdot W]$, the algorithm computes a value $C_{k}[W]$
satisfying the guarantee in Lemma 15.

1:$k:=\lceil\log W\rceil$

2:Initialize $C_{0}[0,\dots,8\Delta]:=\mathcal{P}_{0}[0,\dots,8\Delta]$ by
iterating over the item set $\mathcal{I}$ once

3:for $i=1,\dots,k$ do

4: $A_{i}[W\cdot 2^{i-k}\pm 8\Delta]:=C_{i-1}[W\cdot 2^{i-1-k}\pm
8\Delta]\oplus C_{i-1}[W\cdot 2^{i-1-k}\pm 8\Delta]$

5: $C_{i}[j]:=\begin{cases}\lceil\alpha\cdot 2^{i-k}\rceil+24\Delta&\text{if
}A_{i}[j]>\alpha\cdot 2^{i-k}+24\Delta\\\ -\infty&\text{if
}A_{i}[j]<\alpha\cdot 2^{i-k}-40\Delta\\\
A_{i}[j]&\text{otherwise}\end{cases}$ return $C_{k}[W]$

Due to the clipping, at every step we compute a $(\max,+)$-convolution of
sequences of length $O(\Delta)$ and values in $[O(\Delta)]\cup\\{-\infty\\}$
(after shifting the indices and values appropriately). Furthermore, note that
all convolutions involve monotone non-decreasing sequences. Indeed, as noted
above the starting sequence $C_{0}$ is monotone non-decreasing. Convolving it
with itself produces a monotone non-decreasing sequence again, and the
clipping in line 5 of Algorithm 1 preserves monotonicity. The same argument
applies for further iterations. Thus, the running time of Algorithm 1 is
$O(n+T(\Delta)\log W)$, where $T(\Delta)$ is the running time to compute
BMMaxConv on sequences of length $\Delta$.

Regarding correctness, we claim the following:

######  Claim 14.

For every $i\in[k]$ and every index $j\in[W\cdot 2^{i-k}\pm 8\Delta]\cap[W]$
the following holds:

  * $\blacksquare$

If $\mathcal{P}_{i}[j]\in[\alpha\cdot 2^{i-k}-40\Delta,\alpha\cdot
2^{i-k}+24\Delta]$, then $C_{i}[j]=\mathcal{P}_{i}[j]$.

  * $\blacksquare$

If $\mathcal{P}_{i}[j]>\alpha\cdot 2^{i-k}+24\Delta$, then
$C_{i}[j]=\lceil\alpha\cdot 2^{i-k}\rceil+24\Delta$.

  * $\blacksquare$

If $\mathcal{P}_{i}[j]<\alpha\cdot 2^{i-k}-40\Delta$, then $C_{i}[j]=-\infty$.

Intuitively, the claim says that entries “close” to the (scaled) guess
$\alpha\cdot 2^{i-k}$ get computed exactly, while entries below and above get
clipped appropriately.

  * Proof.

We prove the claim by induction on $i$. In the base case $i=0$, note that
since $\alpha\in[p_{\max}\cdot W]$ and $k=\lceil\log W\rceil$ we have
$\alpha\cdot 2^{-k}\leq p_{\max}\leq\Delta$. Thus, $[\alpha\cdot
2^{-k}-40\Delta,\alpha\cdot 2^{-k}+24\Delta]$ contains the whole interval
$[0,\Delta]$ of possible values of $\mathcal{P}_{0}[j]=C_{0}[j]$ (for any
$0\leq j\leq 8\Delta$).

Now we show that the claim holds for any $1\leq i\leq k$ assuming it holds for
$i-1$. Fix any $j\in[W\cdot 2^{i-k}\pm 8\Delta]$. Note that the thresholding
in line 4 of Algorithm 1 does not increasy any of the entries in $A_{i}$, so
$C_{i}[j]\leq A_{i}[j]$. Moreover, since inductively
$C_{i-1}[j^{\prime}]\leq\mathcal{P}_{i-1}[j^{\prime}]$ for all $j^{\prime}$,
by definition of $A_{i}$ we have $A_{i}[j]\leq\mathcal{P}_{i}[j]$. Hence, we
obtain $C_{i}[j]\leq\mathcal{P}_{i}[j]$. We use this observation to obtain the
claim, by showing an appropriate lower bound for $C_{i}[j]$ in the following.

Pick indices $j_{1},j_{2}$ as guaranteed by Lemma 13. Property (i) of Lemma 13
guarantees that the computation of $A_{i}[j]$ in line 3 of Algorithm 1 looks
at the entries $j_{1},j_{2}$ in $C_{i-1}$. Hence, $A_{i}[j]\geq
C_{i-1}[j_{1}]+C_{i-1}[j_{2}]$.

We proceed by a case distinction on the values of the entries
$\mathcal{P}_{i-1}[j_{1}]$ and $\mathcal{P}_{i-1}[j_{2}]$:

##### Case 1:
$\mathcal{P}_{i-1}[j_{1}],\mathcal{P}_{i-1}[j_{2}]\in[\alpha\cdot
2^{i-1-k}-40\Delta,\alpha\cdot 2^{i-1-k}+24\Delta]$

By the induction hypothesis, both values are computed exactly, that is,
$C_{i-1}[j_{1}]=\mathcal{P}_{i-1}[j_{1}]$ and
$C_{i-1}[j_{2}]=\mathcal{P}_{i-1}[j_{2}]$. Thus, $A_{i}[j]\geq
C_{i-1}[j_{1}]+C_{i-1}[j_{2}]=\mathcal{P}_{i-1}[j_{1}]+\mathcal{P}_{i-1}[j_{2}]=\mathcal{P}_{i}[j]$,
using property (ii) of Lemma 13. Since we observed above that
$A_{i}[j]\leq\mathcal{P}_{i}[j]$, we obtain $A_{i}[j]=\mathcal{P}_{i}[j]$. The
thresholding in line 4 of Algorithm 1 now yields the claim for this case.

##### Case 2: $\mathcal{P}_{i-1}[j_{1}]>\alpha\cdot 2^{i-1-k}+24\Delta$

Property (iii) of Lemma 13 implies that
$|\mathcal{P}_{i-1}[j_{1}]-\mathcal{P}_{i-1}[j_{2}]|\leq 4\Delta$, and hence
$\mathcal{P}_{i-1}[j_{2}]\geq\alpha\cdot 2^{i-1-k}+20\Delta$. Thus, property
(ii) of Lemma 13 implies
$\mathcal{P}_{i}[j]=\mathcal{P}_{i-1}[j_{1}]+\mathcal{P}_{i-1}[j_{2}]>\alpha\cdot
2^{i-k}+24\Delta$. Therefore, we want to show that $C_{i}[j]=\lceil\alpha\cdot
2^{i-k}\rceil+24\Delta$.

By the induction hypothesis, we have $C_{i-1}[j_{1}]=\lceil\alpha\cdot
2^{i-1-k}\rceil+24\Delta$ and $C_{i-1}[j_{2}]\geq\alpha\cdot
2^{i-1-k}+20\Delta$. Hence, $A_{i}[j]\geq
C_{i-1}[j_{1}]+C_{i-1}[j_{2}]>\alpha\cdot 2^{i-k}+40\Delta$. Due to the
thresholding, we conclude that $C_{i}[j]=\lceil\alpha\cdot
2^{i-k}\rceil+24\Delta$, as desired.

##### Case 3: $\mathcal{P}_{i-1}[j_{1}]<\alpha\cdot 2^{i-k}-40\Delta$

Similarly as in case 2, property (iii) of Lemma 13 implies that
$\mathcal{P}_{i-1}[j_{2}]\leq\alpha\cdot 2^{i-1-k}-36\Delta$. Thus,
$\mathcal{P}_{i}[j]=\mathcal{P}_{i-1}[j_{1}]+\mathcal{P}_{i-1}[j_{2}]<\alpha\cdot
2^{i-k}-76\Delta$. Since $C_{i}[j]\leq\mathcal{P}_{i}[j]$, but $C_{i}[j]$
takes values in $\\{-\infty\\}\cup[\alpha\cdot 2^{i-k}\pm 40\Delta]$ it
follows that $C_{i}[j]=-\infty$. ∎

Given the claim, it is easy to see that $C_{k}[W]\geq\alpha$ if and only if
$\mathcal{P}_{k}[W]\geq\alpha$. Along with the running time analysis argued
earlier, we obtain the following lemma.

######  Lemma 15.

Algorithm 1 runs in time $O(n+T(\Delta)\log W)$, where $T(\Delta)$ is the time
complexity of BMMaxConv on sequences of length $\Delta$, and computes a value
$C_{k}[W]$ which satisfies $C_{k}[W]\geq\alpha$ if and only if
$\mathrm{OPT}=\mathcal{P}_{k}[W]\geq\alpha$.

Given Lemma 15, we can do binary search to find the optimal value. This gives
an algorithm for Unbounded Knapsack in time $O((n+T(\Delta))\log
W\log\mathrm{OPT})$. To shave the $\operatorname{polylog}(W,\mathrm{OPT})$
factors and obtain the running time $\widetilde{O}(n+T(\Delta))$ claimed in
Theorem 10, we make use of the following lemma. It allows us to reduce the
capacity of the instance by repeatedly adding copies of the item with maximum
profit-to-weight ratio. Similar results have been shown for general ILPs
[EW20], for Unbounded Knapsack [BHSS18] and for the Coin Change problem
[CH22]. For completeness, we include the proof by Chan and He [CH22, Lemma
4.1].777Both Chan and He [CH22] and Bateni et al. [BHSS18] show that the same
conclusion of the lemma holds if $W>w_{i^{*}}^{2}$, with a slightly more
involved argument. For our purposes, this simple variant is enough.

######  Lemma 16.

Let
$(p_{i^{*}},w_{i^{*}}):=\operatorname*{\arg\\!\max}_{(p,w)\in\mathcal{I}}\tfrac{p}{w}$.
If $W\geq 2w_{\max}^{3}$, then there exists an optimal solution containing
$(p_{i^{*}},w_{i^{*}})$.

  * Proof.

Consider an optimal solution $x$ that does not contain item
$(p_{i^{*}},w_{i^{*}})$. If there is an item $(p_{j},w_{j})$ that appears at
least $w_{i^{*}}$ times in $x$, then we can replace $w_{i^{*}}$ of the copies
of item $(p_{j},w_{j})$ by $w_{j}$ copies of item $(p_{i^{*}},w_{i^{*}})$. By
definition of $(p_{i^{*}},w_{i^{*}})$, this does not decrease the total profit
of the solution, so by optimality of $x$ the new solution $x^{\prime}$ is also
optimal. Therefore, some optimal solution contains $(p_{i^{*}},w_{i^{*}})$.

It remains to consider the case that $x$ contains less than $w_{i^{*}}$ copies
of every item, so its total weight is at most $n\cdot w_{i^{*}}\cdot
w_{\max}$. Note that $n\leq w_{\max}$, because without loss of generality
there is at most one item per distinct weight (otherwise we can keep only the
item with the largest profit for each weight). Thus, the total weight of $x$
is at most $w_{\max}^{3}$. It follows that $W<w_{\max}^{3}+w_{i^{*}}\leq
2w_{\max}^{3}$, since otherwise we could add at least one copy of
$(p_{i^{*}},w_{i^{*}})$ to $x$, contradicting its optimality. ∎

We now put all pieces together: As a preprocessing step we repeatedly add the
item $(p_{i^{*}},w_{i^{*}})$ and decrease $W$ by $w_{i^{*}}$, as long as
$W>2w_{\max}^{3}$. After this preprocessing, we have
$W=O(w_{\max}^{3})=O(\Delta^{3})$, and thus $\mathrm{OPT}\leq W\cdot
p_{\max}=O(\Delta^{4})$. The we do binary search for $\mathrm{OPT}$, using
Algorithm 1 as a decision procedure. By Lemma 15, the overall running time is
$O((n+T(\Delta))\log^{2}\Delta)=\widetilde{O}(n+T(\Delta))$. This completes
the proof of Theorem 10.

###  Solution Reconstruction

The algorithm we described gives us the value $\mathrm{OPT}$ of the optimal
solution. In this section we will describe how to use witness arrays (Lemma 9)
to reconstruct a feasible solution $x\in\mathbb{N}^{n}$ such that
$p(x)=\mathrm{OPT}$ with only a polylogarithmic overhead in the overall
running time.

######  Lemma 17.

A optimal solution $x$ can be reconstructed in time
$\widetilde{O}(n+T(p_{\max}+w_{\max}))$.

  * Proof Sketch.

Let $k=\lceil\log W\rceil$ be as in Algorithm 1. After determining the value
of $\mathrm{OPT}$, run Algorithm 1 again with the guess $\alpha=\mathrm{OPT}$.
For every BMMaxConv in line 4 compute the witness array $M_{i}$ corresponding
to $A_{i}$ via Lemma 9. This takes time
$\widetilde{O}(n+T(p_{\max}+w_{\max}))$. Now, the idea is to start from
$C_{k}[W]$ and traverse the _computation tree_ of Algorithm 1 backwards. That
is, we look at the pair of entries $C_{k-1}[M_{k}[W]],C_{k-1}[W-M_{k}[W]]$
which define the value of $C_{k}[W]$ and recursively obtain the pair of
entries in $C_{k-2}$ determining the value of $C_{k-1}[M_{k}[W]]$, etc. By
proceeding in this way, we eventually hit the leaves, i.e., the entries of
$C_{0}[0,\dots,8\Delta]=\mathcal{P}_{0}[0,\dots,8\Delta]$, which correspond to
the items in an optimal solution. A naive implementation of this idea takes
time $O(\sum_{i\leq k}2^{i})=O(2^{k})=O(W)$, which is too slow.

Now we describe an efficient implementation of the same idea. For each
$i\in[k]$ construct an array $Z_{i}[W\cdot 2^{i-k}\pm 8\Delta]$ initialized to
zeros. Set $Z_{k}[W]:=1$. We will maintain the invariant that $Z_{i}[j]$
stores the number of times we arrive at $C_{i}[j]$ by traversing the
computation tree starting at $C_{k}[W]$. This clearly holds for $Z_{k}[W]=1$
by definition. Now we describe how to fill the entries for the levels below.
Iterate over $i=k,k-1,\dots,1$. For each entry $j\in[W\cdot 2^{i-k}\pm
8\Delta]\cap[W]$ add $Z_{i}[j]$ to its witness entries in the level below,
i.e., increase $Z_{i-1}[M_{i}[j]]$ by $Z_{i}[j]$ and $Z_{i-1}[j-M_{i}[j]]$ by
$Z_{i}[j]$. The invariant is maintained by definition of the witnesses, and
because Algorithm 1 guarantees that $M_{i}[j],j-M_{i}[j]\in[2\cdot
2^{i-1-k}\pm 8\Delta]\cap[W]$. Note that this procedure takes time
$O(k\Delta)=\widetilde{O}(\Delta)$.

Finally, note that for the base case we have that each $Z_{0}[j]$ for
$j\in[8\Delta]$ counts the number of times that we hit the entry
$C_{0}[j]=\mathcal{P}_{0}[j]$ in the computation tree starting from
$C_{k}[W]$. Recall that by definition, $\mathcal{P}_{0}[j]$ is the maximum
profit of an item in $\mathcal{I}$ with weight at most $j$. Hence, every entry
$\mathcal{P}_{0}[j]$ corresponds to a unique item in $\mathcal{I}$. Therefore,
we can read off from $Z_{0}[0,\dots,8\Delta]$ the multiplicity of each item
included in an optimal solution. The overall time of the procedure is
$\widetilde{O}(n+T(p_{\max}+w_{\max}))$, as claimed. ∎

##  Exact Algorithm for 0-1 Knapsack

Cygan et al. [CMWW19] showed the following reduction from 0-1 Knapsack to
BMMaxConv:

######  Theorem 18 ([CMWW19, Theorem 13]).

If MaxConv on length-$n$ sequences can be solved in time $T(n)$, then 0-1
Knapsack can be solved in time $O(T(W\log W)\log^{3}(n/\delta)\log n)$ with
probability at least $1-\delta$.

Their reduction is a generalization of Bringmann’s algorithm for Subset Sum
[Bri17], replacing Boolean convolutions by $(\max,+)$-convolutions. We observe
that essentially the same reduction yields sequences of length $O(W)$ which
are monotone and have entries bounded by $\mathrm{OPT}$. In particular, these
are BMMaxConv instances. This yields the following:

######  Theorem 19 ($\text{{0-1 Knapsack}}{}\rightarrow\text{{BMMaxConv}}{}$).

If BMMaxConv on length-$n$ sequences can be solved in time $T(n)$, then 0-1
Knapsack can be solved in time $\widetilde{O}(n+T(W+\mathrm{OPT}))$ with high
probability.

  * Proof.

The proof is virtually the same as [CMWW19, Theorem 13], so we omit some
details. In particular, we emphasize how the constructed instances can be seen
to be monotone and bounded, but we omit some details of the correctness
argument. The idea of the algorithm is the following: split the item set
$\mathcal{I}$ into groups $G_{(a,b)}\subseteq\mathcal{I}$ such that all items
$(p,w)\in\mathcal{I}$ with $p\in[2^{a-1},2^{a})$ and $w\in[2^{b-1},2^{b})$ are
in group $G_{(a,b)}$. That is, all items within each group have weights and
profits within a factor of 2 of each other, and thus there are $O(\log
W\log\mathrm{OPT})$ many groups. We will describe how to compute
$\mathcal{P}_{G_{(a,b)}}[0,\dots,W]$ for each $G_{(a,b)}$. Having that, we
simply combine all the profit arrays into
$\mathcal{P}_{\mathcal{I}}[0,\dots,W]$ using $(\max,+)$-convolutions. Since we
have $O(\log W\log\mathrm{OPT})$ groups, and each profit array is a monotone
non-decreasing sequence of length $W$ with entries bounded by $\mathrm{OPT}$,
the combination step takes time $\widetilde{O}(T(W+\mathrm{OPT}))$.

Fix some group $G_{(a,b)}$. Since every $(p,w)\in G_{(a,b)}$ has
$w\in[2^{a-1},2^{a})$ and $p\in[2^{b-1},2^{b})$, any feasible solution from
$G_{(a,b)}$ consists of at most
$z:=\lceil\min\\{W/2^{a-1},\mathrm{OPT}/2^{b-1}\\}\rceil$ items. Thus, by
splitting the items in $G_{(a,b)}$ randomly into $z$ subgroups
$G_{(a,b),1},\dots,G_{(a,b),z}$, any fixed feasible solution has at most
$O(\log z)$ items in each subgroup $G_{(a,b),k}$ with high probability. To see
this, fix a solution $x$ and note that,

$\displaystyle\mathop{\bf Pr\/}[\text{at least }r\text{ items from }x\text{
fall in }G_{(a,b),k}]$ $\displaystyle\leq{z\choose
r}\left(\frac{1}{z}\right)^{r}\leq\left(\frac{e\cdot
z}{r}\right)^{r}\left(\frac{1}{z}\right)^{r}=\left(\frac{e}{r}\right)^{r},$

where the first inequality follows due to a union bound over all subsets of
items of size $r$. By setting $r=O(\log z)$, we can bound this probability by
$z^{-c}$ for any constant $c$. So by a union bound, none of the $z$ groups
$G_{(a,b),1},\dots,G_{(a,b),z}$ has more than $\kappa:=O(\log z)$ elements
from the fixed solution $x$ with probability at least
$1-1/\operatorname{poly}(z)$.

Therefore, to obtain the value of any fixed solution it suffices to compute
the optimal solution consisting of at most $\kappa$ items from $G_{(a,b),k}$
for every target weight $\leq O(2^{a}\kappa)$, and then merge the results.
More precisely, for every $1\leq i\leq z$ we compute the array
$\mathcal{P}_{G_{(a,b),i},\log(\kappa)}[0,\dots,O(2^{a}\kappa)]$. Recall that
this is defined as

$\mathcal{P}_{G_{(a,b),i},\log(\kappa)}[j]:=\max\\{p(x)\colon x\text{ is a
solution from }G_{(a,b),i}\text{ with }w(x)\leq j,\|x\|_{1}\leq\kappa\\}$

for each $j\in[O(2^{a}\kappa)]$. For ease of notation, we denote the array by
$\mathcal{P}_{G_{i},\kappa}:=\mathcal{P}_{G_{(a,b),i},\log\kappa}$.

Then, we merge the $\mathcal{P}_{G_{i},\kappa}$’s using
$(\max,+)$-convolutions. Now we describe these two steps in more detail:

##### Computing $\mathcal{P}_{G_{i},\kappa}[0,\dots,O(2^{a}\kappa)]$

Since we only care about solutions with at most $\kappa$ items, we use
randomization again888This step is called “Color Coding” in [Bri17, CMWW19].:
split the items in $G_{(a,b),i}$ into $\kappa^{2}$ buckets
$A_{1},\dots,A_{\kappa^{2}}$. By the birthday paradox, with constant
probability it holds that any fixed solution is shattered among the buckets,
i.e., each bucket contains at most 1 item of the solution. Thus, for each
bucket $A_{k}$ we construct the array $\mathcal{P}_{A_{k},0}[0,\dots,2^{a}]$.
Recall that this is defined as

$\mathcal{P}_{A_{k},0}[j]:=\max\\{p(x)\colon x\text{ is a solution from
}A_{k}\text{ with }w(x)\leq j,\|x\|_{1}\leq 1\\}$

for each entry $j\in[2^{a}]$. To combine the results, we compute
$\mathcal{P}_{A_{1},0}\oplus\mathcal{P}_{A_{2},0}\oplus\dots\oplus\mathcal{P}_{A_{\kappa^{2}},0}$.
By definition, every $\mathcal{P}_{A_{i},0}$ is a monotone non-decreasing
sequence of length $2^{a}$ with entries bounded by $2^{b}$. Thus, the merging
step takes time $O(T((2^{a}+2^{b})\cdot\kappa^{2})\cdot\kappa^{2})$.

Each entry of the resulting array has the correct value
$\mathcal{P}_{i,\kappa}[j]$ with constant probability, since a corresponding
optimal solution is shattered with constant probability. By repeating this
process $O(\log z)$ times and keeping the entrywise maximum among all
repetitions, we boost the success probability to $1-1/\operatorname{poly}(z)$.
Thus, by a union bound over the $z$ subgroups $G_{(a,b),1},\dots,G_{(a,b),z}$,
we get that any $z$ fixed entries
$\mathcal{P}_{G_{1},\kappa}[j_{1}],\dots,\mathcal{P}_{G_{z},\kappa}[j_{z}]$
corresponding to a solution which is partitioned among the $z$ subgroups get
computed correctly with probability at least $1-1/\operatorname{poly}(z)$.
This adds an extra $O(\log z)=O(\kappa)$ factor to the running time.

##### Merging
$\mathcal{P}_{G_{1},\kappa}\oplus\dots\oplus\mathcal{P}_{G_{z},\kappa}$

This computation is done in a binary tree-like fashion. That is, in the first
level we compute
$(\mathcal{P}_{G_{1},\kappa}\oplus\mathcal{P}_{G_{2},\kappa}),(\mathcal{P}_{G_{3},\kappa}\oplus\mathcal{P}_{G_{4},\kappa}),\dots,(\mathcal{P}_{G_{z-1},\kappa}\oplus\mathcal{P}_{G_{z},\kappa})$.
In the second level we merge the results from the first level in a similar
way. We proceed in the same way with further levels. Since we merge $z$
sequences, we have $\lceil\log z\rceil$ levels of computation. In the $j$-th
level, we compute the $(\max,+)$-convolution of $z/2^{j}$ many monotone non-
decreasing sequences of length $O(2^{j}\cdot 2^{a}\cdot\kappa)$ with entries
bounded by $O(2^{j}\cdot 2^{b}\cdot\kappa)$. Therefore, overall the merging
takes time

$O\bigg{(}\sum_{j=1}^{\lceil\log z\rceil}\frac{z}{2^{j}}\cdot
T((2^{a}+2^{b})\cdot
2^{j}\cdot\kappa)\bigg{)}\leq\widetilde{O}(T((2^{a}+2^{b})\cdot z)),$

where we used both of our niceness assumptions $k\cdot T(n)\leq O(T(k\cdot
n))$ for any $k>1$ and $T(\widetilde{O}(n))\leq\widetilde{O}(T(n))$. Since
$z=\lceil\min\\{W/2^{a-1},\mathrm{OPT}/2^{b-1}\\}\rceil$, we have
$\widetilde{O}(T((2^{a}+2^{b})\cdot z)=\widetilde{O}(T(W+\mathrm{OPT}))$.

##### Wrapping up

To recap, the algorithm does the following steps:

  1. 1.

Split the items into $O(\log W\log\mathrm{OPT})$ groups $G_{(a,b)}$. This
takes time $O(n)$.

  2. 2.

Randomly split each group $G_{(a,b)}$ into
$z:=\lceil\min\\{W/2^{a-1},\mathrm{OPT}/2^{b-1}\\}\rceil$ subgroups
$G_{(a,b),i}$ for $i\in[z]$.

  3. 3.

For each $G_{(a,b),i}$ compute the array
$\mathcal{P}_{G_{i},\kappa}[0,\dots,O(2^{a}\kappa)]$ in time
$O(T((2^{a}+2^{b})\kappa^{2})\cdot\kappa^{3})$. Since $\kappa=O(\log z)$, the
total time over all $i\in[z]$ is

$O(z\cdot T((2^{a}+2^{b})\kappa^{2})\cdot\kappa^{3})\leq
O(T((2^{a}+2^{b})\cdot
z\cdot\kappa^{2})\kappa^{3})\leq\widetilde{O}(T((2^{a}+2^{b})\cdot
z))\leq\widetilde{O}(T(W+\mathrm{OPT})).$

Note that here we use the niceness assumptions on $T(n)$. In particular, first
we used that $k\cdot T(n)\leq O(T(k\cdot n))$ for any $k>1$, and then that
$T(\widetilde{O}(n))\leq\widetilde{O}(T(n))$.

  4. 4.

Merge the arrays
$\mathcal{P}_{G_{1},\kappa}\oplus\dots\oplus\mathcal{P}_{G_{z},\kappa}$ in
time $\widetilde{O}(T(W+\mathrm{OPT}))$ to obtain
$\mathcal{P}_{G_{(a,b)}}[0,\dots,W]$.

  5. 5.

Merge the arrays $\mathcal{P}_{G_{(a,b)}}$ using $O(\log W\log\mathrm{OPT})$
convolutions in total time $\widetilde{O}(T(W+\mathrm{OPT}))$.

Thus, the overall time of the algorithm is
$\widetilde{O}(n+T(W+\mathrm{OPT}))$. Note that as mentioned earlier in the
proof, the algorithm succeeds in computing any _fixed_ entry
$\mathcal{P}_{\mathcal{I}}[j]$ with probability at least
$1-1/\operatorname{poly}(z)$. In particular, this is sufficient to compute the
optimal solution $\mathcal{P}_{\mathcal{I}}[W]$ with good probability.

As described, the algorithm only returns the value of the optimal solution. We
can easily reconstruct an optimal solution $x\in\mathbb{N}^{n}$ for which
$p(x)=\mathrm{OPT}$ as we sketch now. Note that at the end of the algorithm,
we will have a sequence whose entries correspond to $\mathcal{P}[0,\dots,W]$.
This sequence was obtained as the BMMaxConv of two distinct other sequences,
call them $A[0,\dots,W],B[0,\dots,W]$. For the output entry $\mathcal{P}[W]$,
we can find its witness $i\in[W]$, i.e. the index $i$ such that
$\mathcal{P}[W]=A[i]+B[W-i]$. Note that we can find $i$ in time $O(W)$ by
simply trying all possibilities. Then, we continue recursively finding the
witnesses for $i$ and for $W-i$. Eventually, we will reach the entries of the
arrays $\mathcal{P}_{A_{k},0}$ which correspond to single items from
$\mathcal{I}$, and these form the solution $x$. The crucial observation is
that because the algorithm never convolves a sequence with itself (unlike our
algorithm for Unbounded Knapsack), this recursive process finds at most one
witness per convolution. Hence, the total time spent is proportional to the
total length of the convolved sequences $\widetilde{O}(W)$. ∎

##  Approximation Schemes for Unbounded Knapsack

###  Preparations

##### Greedy 2-approximation

The fractional solution for an instance $(\mathcal{I},W)$ of Unbounded
Knapsack has a simple structure: pack the entire capacity $W$ greedily with
the _most efficient item_ $i^{*}$. That is, choose the item
$(p_{i^{*}},w_{i^{*}})\in\mathcal{I}$ which maximizes the ratio
$p_{i^{*}}/w_{i^{*}}$ and add it $W/w_{i^{*}}$ many times. Since $\lfloor
W/w_{i^{*}}\rfloor$ copies forms a feasible integral solution, it holds that
$\lfloor W/w_{i^{*}}\rfloor\cdot
p_{i^{*}}\leq\mathrm{OPT}\leq(W/w_{i^{*}})\cdot p_{i^{*}}$. By
$W/w_{i^{*}}\geq 1$, we have $\lfloor W/w_{i^{*}}\rfloor\geq 1/2\cdot
W/w_{i^{*}}$. Thus, the greedy solution is a 2-approximation to
$\mathrm{OPT}$. Note that we can find this solution in time $O(n)$.

##### Connection to MaxConv

Recall that for an integer $i\geq 0$, we defined $\mathcal{P}_{i}[0,\dots,W]$
as $\mathcal{P}_{i}[j]:=\max\\{p(x)\colon w(x)\leq j,\|x\|_{1}\leq 2^{i}\\}$.
The following lemma shows that if we know $\mathcal{P}_{i-1}$, we can compute
$\mathcal{P}_{i}$ by applying a $(\max,+)$-convolution of $\mathcal{P}_{i-1}$
with itself.

######  Lemma 20 (Halving Lemma).

For any $i\geq 1$ and $w\geq 0$, it holds that

$\mathcal{P}_{i}[0,\dots,w]=\mathcal{P}_{i-1}[0,\dots,w]\oplus\mathcal{P}_{i-1}[0,\dots,w].$

  * Proof.

We denote the right hand side by
$C:=\mathcal{P}_{i-1}[0,\dots,w]\oplus\mathcal{P}_{i-1}[0,\dots,w]$. Fix some
$j\in[w]$. We will show that $\mathcal{P}_{i}[j]=C[j]$:

$\mathcal{P}_{i}[j]\geq C[j]$: This holds since $C[j]$ corresponds to the
profit of some solution with at most $2^{i}$ items, but by definition
$\mathcal{P}_{i}[j]$ is the maximum profit among all such solutions.

$\mathcal{P}_{i}[j]\leq C[j]$: Let $x\in\mathbb{N}^{n}$ be the solution
corresponding to $\mathcal{P}_{i}[j]$, i.e. such that
$p(x)=\mathcal{P}_{i}[j]$, $w(x)\leq j$ and $\|x\|_{1}\leq 2^{i}$. Split $x$
in two solutions $x=x_{1}+x_{2}$ of roughly the same size
$\|x_{1}\|\approx\|x_{2}\|_{1}\approx\|x\|_{1}/2$ (if $\|x\|_{1}$ is odd, put
an extra item to $x_{1}$ or $x_{2}$). In this way, it holds that both $x_{1}$
and $x_{2}$ are solutions of at most $2^{i-1}$ items and weight at most $j$
and therefore by the optimality of $\mathcal{P}_{i-1}$ it holds that
$p(x_{1})\leq\mathcal{P}_{i-1}[w(x_{1})]$ and
$p(x_{2})\leq\mathcal{P}_{i-1}[w(x_{2})]$. Hence, by definition of $C$ we
conclude that
$C[j]\geq\mathcal{P}_{i-1}[j-w(x_{2})]+\mathcal{P}_{i-1}[w(x_{2})]\geq
p(x_{1})+p(x_{2})=\mathcal{P}_{i}[j]$. ∎

Since any item has weight at least 1, the optimal solution consists of at most
$W$ items. Thus, we can use Lemma 20 to compute
$\mathrm{OPT}=\mathcal{P}_{\lceil\log W\rceil}[W]$ by applying $O(\log W)$
$(\max,+)$-convolutions (note that the base case $\mathcal{P}_{0}[0,\dots,W]$
corresponds to solutions of at most one item, and thus can be computed
easily). Our approximation schemes will implement this “repeated squaring”
algorithm by appropriately approximating the $(\max,+)$-convolutions.

###  A simplified FPTAS

In this section we prove the following reduction from approximating Unbounded
Knapsack to MaxConv.

######  Theorem 21.

If MaxConv can be solved in time $T(n)$, then Unbounded Knapsack has an FPTAS
in time $\widetilde{O}(n+T(1/\varepsilon))$.

This proves Theorem 3 by plugging in the bound $n^{2}/2^{\Omega(\sqrt{\log
n})}$ for MaxConv [BCD+14, Wil18].

####  Preprocessing

To give the FPTAS we start with some preprocessing to remove items with small
profit and items with small weight.

##### Step 1: Remove cheap items

We first remove items with small profit. Let $P_{0}$ be the value of the
greedy 2-approximation and set $T:=2\varepsilon P_{0}$. Split the items into
_expensive_ $\mathcal{I}_{E}:=\\{(p,w)\in\mathcal{I}\colon p>T\\}$, and
_cheap_ $\mathcal{I}_{C}:=\mathcal{I}\setminus\mathcal{I}_{E}$. Let
$i^{*}:=\operatorname*{\arg\\!\max}_{i\in\mathcal{I}_{C}}\frac{p_{i}}{w_{i}}$
be the item corresponding to the greedy 2-approximation for the cheap items
and set $r:=\lceil T/p_{i^{*}}\rceil$. We delete all cheap items from
$\mathcal{I}$ and add an item corresponding to $r$ copies of
$(p_{i^{*}},w_{i^{*}})$, i.e., we set
$\mathcal{I}^{\prime}:=\mathcal{I}_{E}\cup\\{(r\cdot p_{i^{*}},r\cdot
w_{i^{*}})\\}$. Note that now any item in $\mathcal{I}^{\prime}$ has profit at
least $T$. These steps are summarized in Algorithm 2. The following lemma
shows that this decreases the total profit of any solution by at most
$O(\varepsilon\cdot\mathrm{OPT})$.

Algorithm 2 $\textsc{Preprocessing-Profits}(\mathcal{I},W)$: Preprocessing to
remove low profit items.

1:Let $P_{0}$ be the value of the greedy 2-approximation of $(\mathcal{I},W)$

2:$T:=2\cdot\varepsilon\cdot P_{0}$

3:$\mathcal{I}_{E}:=\\{(p,w)\in\mathcal{I}\colon
p>T\\},\mathcal{I}_{C}:=\mathcal{I}\setminus\mathcal{I}_{E}$

4:$i^{*}:=\operatorname*{\arg\\!\max}_{i\in\mathcal{I}_{C}}\frac{p_{i}}{w_{i}}$

5:$r:=\lceil T/p_{i^{*}}\rceil$

6:return $\mathcal{I}_{E}\cup\\{(r\cdot p_{i^{*}},r\cdot w_{i^{*}})\\}$

######  Lemma 22 (Preprocessing Profits).

Let $\mathcal{I}^{\prime}$ be the result of running Algorithm 2 on
$(\mathcal{I},W)$. Then, for every $w\in[W]$, it holds that
$\mathcal{P}_{\mathcal{I}^{\prime}}[w]\geq\mathcal{P}_{\mathcal{I}}[w]-4\varepsilon\cdot\mathrm{OPT}$.
Moreover, the minimum profit in $\mathcal{I}^{\prime}$ is
$p_{\min}>\varepsilon\mathrm{OPT}$.

  * Proof.

Fix some weight $w\in[W]$ and let $x\in\mathbb{N}^{|\mathcal{I}|}$ be the
solution from $\mathcal{I}$ corresponding to the entry
$\mathcal{P}_{\mathcal{I}}[w]$. We denote by $x_{C}$ the _cheap_ items in $x$,
i.e., those with profit $\leq T=2\varepsilon P_{0}$. Thus, we can write
$w_{\mathcal{I}}(x)=w_{\mathcal{I}}(x_{C})+w_{\mathcal{I}}(x-x_{C})$ and
similarly
$p_{\mathcal{I}}(x)=p_{\mathcal{I}}(x_{C})+p_{\mathcal{I}}(x-x_{C})$.

Now we construct a solution $x^{\prime}\in\mathbb{N}^{|\mathcal{I}^{\prime}|}$
from the preprocessed $\mathcal{I}^{\prime}$ which will satisfy
$w_{\mathcal{I}^{\prime}}(x^{\prime})\leq w$ and
$p_{\mathcal{I}^{\prime}}(x^{\prime})\geq p-\varepsilon\cdot\mathrm{OPT}$,
yielding the lemma. We start from $x$ and remove all the cheap items $x_{C}$,
replacing them by $\lfloor w_{\mathcal{I}}(x_{C})/(r\cdot
w_{i^{*}})\rfloor$-many copies of $(r\cdot p_{i^{*}},r\cdot
w_{i^{*}})\in\mathcal{I}^{\prime}$. Note that in this way,
$w_{\mathcal{I}^{\prime}}(x^{\prime})\leq w$. Now we lower bound the profit.
Since $(p_{i^{*}},w_{i^{*}})$ is the item corresponding to the greedy
2-approximation from the cheap items, it follows that
$p_{\mathcal{I}}(x_{C})\leq\frac{w_{\mathcal{I}}(x_{C})}{w_{i^{*}}}\cdot
p_{i^{*}}$. Further, by definition of $r$ it holds that $r\leq T/p_{i^{*}}+1$.
Thus,

$p_{\mathcal{I}^{\prime}}(x^{\prime})=p_{\mathcal{I}}(x-x_{C})+r\cdot
p_{i^{*}}\cdot\lfloor w(x_{C})/(r\cdot w_{i^{*}})\rfloor\geq
p_{\mathcal{I}}(x-x_{C})+p_{\mathcal{I}}(x_{C})-r\cdot p_{i^{*}}\geq
p_{\mathcal{I}}(x)-T-p_{i^{*}}.$

Since $p_{i^{*}}\leq T=2\varepsilon\cdot P_{0}$, we conclude that
$p_{\mathcal{I}^{\prime}}(x^{\prime})\geq p_{\mathcal{I}}(x)-4\varepsilon\cdot
P_{0}$. Therefore, $\mathcal{P}_{\mathcal{I}^{\prime}}[w]\geq
p_{\mathcal{I}^{\prime}}(x^{\prime})\geq p_{\mathcal{I}}(x)-4\varepsilon\cdot
P_{0}\geq\mathcal{P}_{\mathcal{I}}[w]-4\varepsilon\cdot\mathrm{OPT}$, as
desired.

Finally, note that by construction we have that $p_{\min}>2\varepsilon
P_{0}\geq\varepsilon\mathrm{OPT}$. ∎

##### Step 2: Remove light items

Having removed all items with low profit, we proceed similarly to remove items
of low weight. More precisely, we say that an item is light if its weight is
less than $\varepsilon\cdot W$. We remove all light items except for the most
profitable one (i.e. the one with the best profit to weight ratio), which we
_copy_ enough times to make it have weight at least $\varepsilon\cdot W$. The
details are shown in Algorithm 3.

Algorithm 3 $\textsc{Preprocessing-Profits-And-Weights}(\mathcal{I},W)$:
Preprocessing to remove items of low profit and low weight.

1:$\widetilde{\mathcal{I}}:=\textsc{Preprocessing-Profits}(\mathcal{I},W)$
(Algorithm 2)

2:$\mathcal{I}_{L}:=\\{(p,w)\in\widetilde{\mathcal{I}}\colon
w<\varepsilon\cdot
W\\},\mathcal{I}_{H}:=\widetilde{\mathcal{I}}\setminus\mathcal{I}_{S}$

3:$i^{*}:=\operatorname*{\arg\\!\max}_{i\in\mathcal{I}_{L}}\frac{p_{i}}{w_{i}}$

4:$r:=\lceil\frac{\varepsilon\cdot W}{w_{i^{*}}}\rceil$

5:return $\mathcal{I}_{H}\cup\\{(r\cdot p_{i^{*}},r\cdot w_{i^{*}})\\}$

The following lemma shows that removing cheap and light items as in Algorithm
3 only decreases the profit of any solution by $O(\varepsilon\mathrm{OPT})$.

######  Lemma 23 (Preprocessing Profits and Weights).

Let $\mathcal{I}^{\prime}$ be the result of running Algorithm 3 on
$(\mathcal{I},W)$. Then any solution for $\mathcal{I}^{\prime}$ has a
corresponding solution for $\mathcal{I}$ with the same profit and weight.
Further, for any $w\in[W]$ it holds that
$\mathcal{P}_{\mathcal{I}^{\prime}}[w]\geq\mathcal{P}_{\mathcal{I}}[w]-8\varepsilon\cdot\mathrm{OPT}$.
Moreover, the minimum profit and minimum weight in $\mathcal{I}^{\prime}$
satisfy $p_{\min}>\varepsilon\mathrm{OPT}$ and $w_{\min}>\varepsilon W$.

  * Proof.

Fix $w\in[W]$ and $p:=\mathcal{P}_{\mathcal{I}}[w]$. After running Algorithm 2
in Line 1, by Lemma 22, we know that there is a solution $x$ from
$\widetilde{\mathcal{I}}$ with $p_{\widetilde{\mathcal{I}}}(x)\geq
p-4\varepsilon\cdot\mathrm{OPT}$ and $w_{\widetilde{\mathcal{I}}}(x)\leq w$.
Let $x_{L}$ be the light items in $x$, i.e., those with weight
$<\varepsilon\cdot W$. We construct a solution $x^{\prime}$ of items from
$\mathcal{I}^{\prime}$ by taking $x$, removing all the items in $x_{L}$ and
replacing them by $\lfloor w_{\widetilde{\mathcal{I}}}(x_{L})/(r\cdot
w_{i^{*}})\rfloor$-many copies of $(r\cdot p_{i^{*}},r\cdot w_{i^{*}})$. Then,
the total profit of $x^{\prime}$ is

$\displaystyle p_{\mathcal{I}^{\prime}}(x^{\prime})$
$\displaystyle=p_{\widetilde{\mathcal{I}}}(x-x_{L})+\left\lfloor\frac{w_{\widetilde{\mathcal{I}}}(x_{L})}{r\cdot
w_{i^{*}}}\right\rfloor\cdot r\cdot p_{i^{*}}\geq
p_{\widetilde{\mathcal{I}}}(x-x_{L})+\frac{w_{\widetilde{\mathcal{I}}}(x_{L})}{r\cdot
w_{i^{*}}}\cdot r\cdot p_{i^{*}}-r\cdot p_{i^{*}}$ $\displaystyle\geq
p_{\widetilde{\mathcal{I}}}(x-x_{L})+p_{\widetilde{\mathcal{I}}}(x_{L})-r\cdot
p_{i^{*}}=p_{\widetilde{\mathcal{I}}}(x)-r\cdot p_{i^{*}},$ (2)

where the second inequality $p(x_{L})\leq\frac{w(x_{L})}{r\cdot
w_{i^{*}}}\cdot r\cdot p_{i^{*}}$ follows since by definition
$(p_{i^{*}},w_{i^{*}})$ is the most efficient of the light items. Now we argue
that we can bound the last term $p_{i^{*}}\cdot r$ by
$O(\varepsilon\mathrm{OPT})$. As $w_{i^{*}}$ is a light item, we have
$w_{i^{*}}\leq\varepsilon W$. Since for any number $z\geq 1$ we have that
$\lceil z\rceil\leq 2z$, it follows that $r=\lceil(\varepsilon
W)/w_{i^{*}}\rceil\leq 2\varepsilon W/w_{i^{*}}$. Since packing $\lfloor
W/w_{i^{*}}\rfloor$ copies of item $i^{*}$ is a feasible solution, it holds
that $\mathrm{OPT}\geq\lfloor W/w_{i^{*}}\rfloor
p_{i^{*}}\geq\tfrac{Wp_{i^{*}}}{2w_{i^{*}}}$. Combining both inequalities we
get that $r\cdot p_{i^{*}}\leq 2\varepsilon Wp_{i^{*}}/w_{i^{*}}\leq
4\varepsilon\cdot\mathrm{OPT}$. Therefore, by (2) we conclude that
$p_{\mathcal{I}^{\prime}}(x^{\prime})\geq
p_{\widetilde{\mathcal{I}}}(x)-r\cdot p_{i^{*}}\geq
p_{\widetilde{\mathcal{I}}}(x)-4\varepsilon\cdot\mathrm{OPT}\geq
p-8\varepsilon\cdot\mathrm{OPT}$.

Similarly, we can bound the total weight of $x^{\prime}$ as

$w_{\mathcal{I}^{\prime}}(x^{\prime})=w_{\widetilde{\mathcal{I}}}(x-x_{L})+\left\lfloor\frac{w_{\widetilde{\mathcal{I}}}(x_{L})}{r\cdot
w_{i^{*}}}\right\rfloor\cdot r\cdot w_{i^{*}}\leq
w_{\widetilde{\mathcal{I}}}(x-x_{L})+w_{\widetilde{\mathcal{I}}}(x_{L})\leq
w_{\widetilde{\mathcal{I}}}(x)\leq w.$

Finally, note that $p_{\min}>\varepsilon\mathrm{OPT}$ follows directly from
Lemma 22 and $w_{\min}>\varepsilon W$ by construction. ∎

####  The Algorithm

To obtain the FPTAS, we first preprocess the set of items $\mathcal{I}$ using
Algorithm 3 and obtain a set $\mathcal{I}^{\prime}$. Then, by Lemma 23, it
holds that
$\mathcal{P}_{\mathcal{I}^{\prime}}[W]\geq(1-O(\varepsilon))\cdot\mathrm{OPT}$,
so to obtain a $(1+O(\varepsilon))$-approximation of
$\mathcal{P}_{\mathcal{I}}[W]$ it suffices to give a
$(1+\varepsilon)$-approximation of $\mathcal{P}_{\mathcal{I}^{\prime}}[W]$.

In fact, we solve a slightly more general problem, and compute a sequence
which gives a (pointwise) $(1+\varepsilon)$-approximation of the entire
sequence $\mathcal{P}_{\mathcal{I}^{\prime}}[0,\dots,W]$, according to the
following definition.

######  Definition 1 (Strong Approximation of a Sequence).

We say that a sequence $A[0,\dots,n]$ (pointwise)
$(1+\varepsilon)$-approximates a sequence $B[0,\dots,n]$ if
$B[i]/(1+\varepsilon)\leq A[i]\leq B[i]$ for every $i\in[n]$.

Our main ingredient will be the following approximate $(\max,+)$-convolution
from [Cha18] (the proof is very similar to that of Lemma 28, which we give in
the next section).

######  Lemma 24 ([Cha18, Item (i) from Lemma 1]).

Let $A[0,\dots,n],B[0,\dots,n]$ be two monotone non-decreasing sequences with
$t_{1}$ and $t_{2}$ steps, respectively. Let $p_{\max},p_{\min}$ be the
maximum and minimum non-zero values in $A,B$. Then, for any
$\varepsilon\in(0,1)$ a monotone non-decreasing sequence $C$ with
$O(1/\varepsilon\cdot\log(p_{\max}/p_{\min}))$ steps which gives a (pointwise)
$1+O(\varepsilon)$-approximation of $A\oplus B$ can be computed in time

$O((t_{1}+t_{2}+T(1/\varepsilon))\cdot\log(p_{\max}/p_{\min}))$

where $T(n)$ is the time needed to compute the $(\min,+)$-convolution of two
length-$n$ sequences.

Now we are ready to describe the main routine. Since after the preprocessing
we have that $w_{\min}>\varepsilon W$, any feasible solution contains at most
$W/w_{\min}<1/\varepsilon$ items. Thus, to approximate the optimal solution in
$\mathcal{I}^{\prime}$, we apply Lemma 20 for $O(\log 1/\varepsilon)$
iterations, but replace the $(\max,+)$-convolutions with the approximate ones
from Lemma 24. The pseudocode is written in Algorithm 4.

Algorithm 4 $\textsc{FPTAS}(\mathcal{I},W)$: Given an instance
$(\mathcal{I},W)$ of Unbounded Knapsack with $w_{\min}>\varepsilon W$, the
algorithm returns a $(1+O(\varepsilon))$-approximation of
$\mathcal{P}_{\mathcal{I}}[0,\dots,W]$

1:Initialize $S_{0}:=\mathcal{P}_{0}[0,\dots,W]$, stored implicitly

2:for $i=1,\dots,\lceil\log 1/\varepsilon\rceil$ do

3: Approximate $S_{i}:=(S_{i-1}\oplus S_{i-1})[0,\dots,W]$

4: using Lemma 24 with error parameter
$\varepsilon^{\prime}:=\varepsilon/\log(1/\varepsilon)$

5:return $S_{\lceil\log 1/\varepsilon\rceil}[0,\dots,W]$

######  Lemma 25.

Let $(\mathcal{I},W)$ be an instance of Unbounded Knapsack on $n$ items with
$p_{\min}>\varepsilon\mathrm{OPT}$ and $w_{\min}>\varepsilon W$. Then, on
input $(\mathcal{I},W)$ Algorithm 4 computes a pointwise
$(1+O(\varepsilon))$-approximation of $\mathcal{P}_{\mathcal{I}}[0,\dots,W]$
in time $\widetilde{O}(n+T(1/\varepsilon))$, where $T(n)$ is the time to
compute BMMaxConv on length-$n$ sequences.

  * Proof.

First we argue about correctness. We claim that if the $(\max,+)$-convolutions
of 4 were _exact_ , then for each $i$ we have that
$S_{i}=\mathcal{P}_{i}[0,\dots,W]$. For the base case $i=0$, this holds by
definition. For further iterations, this holds inductively by Lemma 20. Since
we replaced the exact computations with approximate ones with error parameter
$\varepsilon^{\prime}=\varepsilon/\log(1/\varepsilon)$, and since there are
$O(\log 1/\varepsilon)$ iterations where the error accumulates
multiplicatively, we conclude that $S_{\lceil\log
1/\varepsilon\rceil}[0,\dots,W]$ is a pointwise
$(1+\varepsilon^{\prime})^{O(\log(1/\varepsilon))}=1+O(\varepsilon^{\prime}\log(1/\varepsilon))=(1+O(\varepsilon))$-approximation
of $\mathcal{P}_{\lceil\log 1/\varepsilon\rceil}[0,\dots,W]$. Finally note
that since we assume that $w_{\min}>\varepsilon W$, any feasible solution
consists of at most $W/w_{\min}<1/\varepsilon$ items, which implies that
$\mathcal{P}_{\lceil\log
1/\varepsilon\rceil}[0,\dots,W]=\mathcal{P}[0,\dots,W]$.

Now we argue about the running time. The initialization in line 1 takes time
$O(n)$, since by definition $\mathcal{P}_{0}[0,\dots,W]$ has $n$ steps
corresponding to the $n$ solutions containing one item. Next, we look at the
for-loop. For each iteration, we use Lemma 24 to approximate the convolutions.
Note that each application involves sequences with
$O(n+1/\varepsilon\log(p^{*}/p_{\min}))$ steps by the guarantee of Lemma 24
(the $n$ term arising from the steps of $S_{0}$) where $p^{*}$ is the maximum
entry in any of the involved sequences. Since each entry in any of the
sequences corresponds to a feasible solution for the instance, we have that
$p^{*}\leq\mathrm{OPT}$. Moreover by assumption we have that
$p_{\min}\geq\varepsilon\mathrm{OPT}$, and hence $p^{*}/p_{\min}\leq
O(1/\varepsilon)$. Therefore, each iteration takes time
$\widetilde{O}(n+1/\varepsilon+T(1/\varepsilon))$ and the overall time is
bounded by

$\sum_{i=1}^{\lceil\log\frac{1}{\varepsilon}\rceil}\widetilde{O}\left(n+\tfrac{1}{\varepsilon}+T(1/\varepsilon)\right)=\widetilde{O}(n+T(1/\varepsilon)).$

Note that in this proof we are using the niceness assumption that
$T(\widetilde{O}(n))=\widetilde{O}(T(n))$ as mentioned in Section 2. ∎

We put the pieces together to conclude the proof of the main theorem of this
section.

  * Proof of Theorem 21.

Given a instance of $(\mathcal{I},W)$ of Unbounded Knapsack, we first run the
preprocessing from Algorithm 3 and obtain a new instance
$(\mathcal{I}^{\prime},W)$. Then, we run Algorithm 4 on
$(\mathcal{I}^{\prime},W)$ and obtain a sequence $S[0,\dots,W]$. We claim that
$S[W]$ gives the desired $(1+O(\varepsilon))$-approximation to $\mathrm{OPT}$
in the desired running time.

To see the running time, note that after the preprocessing it holds that
$p_{\min}>2\varepsilon P_{0}\geq\varepsilon\mathrm{OPT}$ and
$w_{\min}>\varepsilon W$. Hence, we can apply Lemma 25 and conclude that the
procedure runs in the desired running time. To argue about correctness, note
that by Lemma 23 it holds that
$\mathcal{P}_{\mathcal{I}^{\prime}}[W]\geq(1-8\varepsilon)\mathrm{OPT}$.
Combining this with the fact that $S[0,\dots,W]$
$(1+O(\varepsilon))$-approximates
$\mathcal{P}_{\mathcal{I}^{\prime}}[0,\dots,W]$ due to Lemma 25, we conclude
that

$S[W]\geq\frac{\mathcal{P}_{\mathcal{I}^{\prime}}[W]}{1+O(\varepsilon)}\geq\frac{(1-8\varepsilon)\mathrm{OPT}}{1+O(\varepsilon)}\geq\frac{\mathrm{OPT}}{1+O(\varepsilon)},$

as desired. ∎

###  Faster Weak FPTAS

In this section we prove the following theorem.

######  Theorem 26.

If BMMaxConv can be solved in time $T(n)$, then Unbounded Knapsack has a weak
approximation scheme in time $\widetilde{O}(n+T(1/\varepsilon))$.

Note that Theorem 4 follows as an immediate corollary by plugging in Chi,
Duan, Xie and Zhang’s algorithm (Theorem 8).

####  The Algorithm

Our approach is similar to the FPTAS from the previous section. The main
difference is that since now we can overshoot the weight constraint by an
additive term of $\varepsilon W$, we can afford to round the weights of the
items. By doing so, we can adapt the algorithm from Lemma 24 to use an
algorithm for BMMaxConv.

We start by specifying the notion of approximation for monotone sequences we
will be working with. In the following definition, it is helpful to think of
the indices as weights and the entries as profits.

######  Definition 2 (Weak Approximation of a Sequence).

We say that a sequence $A[0,\dots,n^{\prime}]$ _weakly_
$(1+\varepsilon)$-approximates a sequence $B[0,\dots,n]$ if the following two
properties hold:

  * (i)

(Good approximation for every entry) For every $j\in[n]$, there exists
$j^{\prime}\in[n^{\prime}]$ with $A[j^{\prime}]\geq B[j]/(1+\varepsilon)$ and
$j^{\prime}\leq(1+\varepsilon)j$.

  * (ii)

(No approximate entry is better than a true entry) For every
$j^{\prime}\in[n^{\prime}]$, there exists $j\in[n]$ such that
$A[j^{\prime}]\leq B[j]$ and $j^{\prime}\geq j$.

The following lemma shows that our notion of weak approximations is
transitive. In particular, it implies that a weak approximation of the
$(\max,+)$-convolution of two weakly approximated sequences gives a (slightly
worse) weak approximation of the convolution of the original sequences.

######  Lemma 27.

If $A$ weakly $(1+\varepsilon)$-approximates $B$ and $B$ weakly
$(1+\varepsilon^{\prime})$-approximates $C$, then $A$ weakly
$(1+\varepsilon)(1+\varepsilon^{\prime})$-approximates $C$.

  * Proof.

First we check that $A$ and $C$ satisfy property (i) of Definition 2. Fix an
entry $C[k]$. Since $B$ weakly $(1+\varepsilon^{\prime})$-approximates $C$, by
property (i) there exists an index $j$ such that $B[j]\geq
C[k]/(1+\varepsilon^{\prime})$ and $j\leq(1+\varepsilon^{\prime})k$. Thus,
since $A$ weakly $(1+\varepsilon)$-approximates $B$ we apply property (i) once
more to conclude that there is an index $i$ such that $A[i]\geq
B[j]/(1+\varepsilon)\geq\tfrac{C[k]}{(1+\varepsilon)(1+\varepsilon^{\prime})}$
and $i\leq(1+\varepsilon)j\leq(1+\varepsilon)(1+\varepsilon^{\prime})k$.

We can similarly check that $A$ and $C$ satisfy property (ii). Fix an entry
$A[i]$ and apply property (ii) to obtain an index $j$ such that $A[i]\leq
B[j]$ and $i\geq j$. Applying property (ii) once more to $j$ yields an index
$k$ such that $B[j]\leq C[k]$ and $j\geq k$. Combining, we conclude that
$A[i]\leq C[k]$ and $i\geq k$, as desired. ∎

We extend Lemma 24 to give a weak approximation of the $(\max,+)$-convolution
of two sequences. Given two pairs of integers $(w,p),(w^{\prime},p^{\prime})$,
we say that $(w,p)$ _dominates_ $(w^{\prime},p^{\prime})$ if $w\leq
w^{\prime}$ and $p>p^{\prime}$. Given a list of pairs
$D=[(w_{1},p_{1}),\dots,(w_{m},p_{m})]$, we can remove all dominated pairs
from $D$ in near-linear time for example by sorting.

######  Lemma 28.

Let $A[0,\dots,N],B[0,\dots,N]$ be two monotone non-decreasing sequences with
$t_{1}$ and $t_{2}$ steps, respectively. Let $p_{\max},p_{\min}$ be the
maximum and minimum non-zero values in $A,B$ and let $w_{\min}=\min\\{i\mid
A[i]\neq 0\text{ or }B[i]\neq 0\\}$. Then, for any $\varepsilon\in(0,1)$ a
monotone non-decreasing sequence $C$ which is a weak
$1+O(\varepsilon)$-approximation of $(A\oplus B)[0,\dots,2N]$ and consists of
$O(1/\varepsilon\cdot\log(p_{\max}/p_{\min})\cdot\log(N/w_{\min}))$ steps can
be computed in time

$O((t_{1}+t_{2}+T(1/\varepsilon))\cdot\log(p_{\max}/p_{\min})\log(N/w_{\min}))$

where $T(n)$ is the time needed to compute BMMaxConv on sequences of length
$n$.

  * Proof.

Let $C:=A\oplus B$. For this proof it will be convenient to work directly with
the steps of the monotone sequences $A,B$ and $C$. So suppose we are given $A$
as a list of steps $A=[(w_{1},p_{1}),\dots,(w_{t_{1}},p_{t_{1}})]$ where each
step $(w,p)$ represents an entry $p=A[w]$ at which $A$ changes, i.e.,
$A[w-1]<A[w]$ (or $w=0$). Similarly, $B$ and $C$ are represented as lists of
steps.

Fix integers $p^{*},w^{*}>0$ and define a sequence of steps $A^{\prime}$ by
keeping every step $(w,p)\in A$ with $w\leq w^{*}$ and $p\leq p^{*}$ and
rounding it to $(\lceil w/(\varepsilon w^{*})\rceil,\lfloor p/(\varepsilon
p^{*})\rfloor)$. Let $B^{\prime}$ be defined analogously. Compute
$C^{\prime}:=A^{\prime}\oplus B^{\prime}$, and scale each step
$(w^{\prime},p^{\prime})\in C^{\prime}$ back, i.e., set
$w:=w^{\prime}\cdot(\varepsilon w^{*})$ and $p:=p\cdot(\varepsilon p^{*})$,
obtaining a sequence of steps $C^{\prime\prime}$. We claim that:

    * (a)

For every step $(w,p)\in C$ for which $w^{*}/2\leq w\leq w^{*}$ and
$p^{*}/2\leq p\leq p^{*}$, there is a step
$(w^{\prime\prime},p^{\prime\prime})\in C^{\prime\prime}$ such that
$w^{\prime\prime}\leq(1+4\varepsilon)w$ and $p^{\prime\prime}\geq
p/(1+8\varepsilon)$.

    * (b)

For every step $(w^{\prime\prime},p^{\prime\prime})\in C^{\prime\prime}$ there
is a step $(w,p)\in C$ such that $w^{\prime\prime}\geq w$ and
$p^{\prime\prime}\leq p$.

To see (a), fix one such step $(w,p)\in C$ and let $(w_{a},p_{a})\in
A,(w_{b},p_{b})\in B$ be the corresponding steps such that $w=w_{a}+w_{b}$ and
$p=p_{a}+p_{b}$. Note that $(w_{a},p_{a})$ has a corresponding rounded step
$(w_{a}^{\prime},p_{a}^{\prime})\in A^{\prime}$ since $w\leq w^{*}$ and $p\leq
p^{*}$ imply that $(w_{a},p_{a})$ were included (after rounding) to
$A^{\prime}$. Similarly, $(w_{b},p_{b})$ has a corresponding step
$(w_{b}^{\prime},p_{b}^{\prime})\in B^{\prime}$. Hence
$C^{\prime}[w_{a}^{\prime}+w_{b}^{\prime}]\geq p_{a}^{\prime}+p_{b}^{\prime}$,
and therefore there is a step $(w_{c}^{\prime\prime},p_{c}^{\prime\prime})\in
C^{\prime\prime}$ such that

$w_{c}^{\prime\prime}\leq(w_{a}^{\prime}+w_{b}^{\prime})\cdot\varepsilon
w^{*}\leq(w/(\varepsilon w^{*})+2)\cdot\varepsilon
w^{*}\leq(1+4\varepsilon)w,$

where we used the definition of $w^{\prime}_{a},w^{\prime}_{b}$ in the second
inequality, and $w^{*}/2\leq w$ in the last one. Similarly, we have that

$p_{c}^{\prime\prime}\geq(p_{a}^{\prime}+p_{b}^{\prime})\cdot\varepsilon
p^{*}\geq(p/(\varepsilon p^{*})-2)\cdot\varepsilon
p^{*}\geq(1-4\varepsilon)p\geq p/(1+8\varepsilon),$

where in the last step we assumed $\varepsilon\leq\frac{1}{8}$, which is
without loss of generality. This proves (a).

Part (b) follows because each step $(w^{\prime\prime},p^{\prime\prime})\in
C^{\prime\prime}$ is a (scaled) sum of steps
$(w_{a}^{\prime},p_{a}^{\prime})\in A^{\prime}$ and
$(w_{b}^{\prime},p_{b}^{\prime})\in B^{\prime}$ which by construction are
rounded steps $(w_{a},p_{a})\in A,(w_{b},p_{b})\in B$. Thus,

$\displaystyle w^{\prime\prime}$
$\displaystyle=(w_{a}^{\prime}+w_{b}^{\prime})\cdot\varepsilon w^{*}=(\lceil
w_{a}/(\varepsilon w^{*})\rceil+\lceil w_{b}/(\varepsilon
w^{*})\rceil)\cdot\varepsilon w^{*}\geq w_{a}+w_{b},$ $\displaystyle
p^{\prime\prime}$
$\displaystyle=(p_{a}^{\prime}+p_{b}^{\prime})\cdot\varepsilon p^{*}=(\lfloor
p_{a}/(\varepsilon p^{*})\rfloor+\lfloor p_{b}/(\varepsilon
p^{*})\rfloor)\cdot\varepsilon p^{*}\leq p_{a}+p_{b},$

which implies that there is a step $(w,p)\in C$ such that $w\leq
w_{a}+w_{b}\leq w^{\prime\prime}$ and $p\geq p_{a}+p_{b}\geq
p^{\prime\prime}$.

The claim implies that if we apply the described procedure for every
$w_{\min}\leq w^{*}\leq 2N$ and $p_{\min}\leq p^{*}\leq p_{\max}$ which are
powers of 2 and combine the results by keeping the set of non-dominated steps,
we obtain a weak $(1+O(\varepsilon))$-approximation of $C$. Indeed, part (a)
implies property (i) of Definition 2 and part (b) implies property (ii). The
overall procedure is summarized in Algorithm 5.

Now we analyze the running time. For each $p^{*}$ and $w^{*}$, we spend
$O(t_{1}+t_{2})$ time to construct $A^{\prime}$ and $B^{\prime}$ in lines 6
and 7. The key step is the computation of $C^{\prime}$ in line 9. Note that
the steps constructed in line 6 for $A^{\prime}$ define a monotone sequence
$A^{\prime}[1,\dots,\lfloor 1/\varepsilon\rfloor]$ where
$A^{\prime}[i]:=\max\\{p^{\prime}\colon(w^{\prime},p^{\prime})\in
A^{\prime},w^{\prime}\leq i\\}$, and $B^{\prime}[1,\dots,\lfloor
1/\varepsilon\rfloor]$ is defined similarly. Thus, $A^{\prime},B^{\prime}$ are
monotone non-decreasing sequences of length $O(1/\varepsilon)$, and due to the
rounding their entries are bounded by $O(1/\varepsilon)$. Thus, we can compute
$C^{\prime}$ in time $T(1/\varepsilon)$ and the overall running time of the
algorithm is
$O((t_{1}+t_{2}+T(1/\varepsilon))\cdot\log(p_{\max}/{p_{\min}})\log(N/w_{\min}))$.
∎

Algorithm 5 Given monotone non-decreasing sequences $A,B$ represented as lists
of steps, the algorithm returns the steps of a weak
$(1+O(\varepsilon))$-approximation of $A\oplus B$.

1:$S:=[\;]$

2:for $i=0,1,2,\dots,\lceil\log(p_{\max}/p_{\min})\rceil$ do

3: $p^{*}:=2^{i}\cdot p_{\min}$

4: for $j=0,1,2,\dots,\lceil\log(N/w_{\min})\rceil$ do

5: $w^{*}:=2^{j}\cdot w_{\min}$

6: $A^{\prime}:=\big{[}(\lceil\tfrac{w}{\varepsilon\cdot
w^{*}}\rceil,\lfloor\tfrac{p}{\varepsilon\cdot p^{*}}\rfloor)\mid(w,p)\in
A,\;w\leq w^{*},p\leq p^{*}\big{]}$

7: $B^{\prime}:=\big{[}(\lceil\tfrac{w}{\varepsilon\cdot
w^{*}}\rceil,\lfloor\tfrac{p}{\varepsilon\cdot p^{*}}\rfloor)\mid(w,p)\in
B,\;w\leq w^{*},p\leq p^{*}\big{]}$

8: Remove dominated pairs from $A^{\prime}$ and $B^{\prime}$

9: Compute $C^{\prime}:=A^{\prime}\oplus B^{\prime}$ using Theorem 8

10: $C^{\prime\prime}:=[(w\cdot\varepsilon w^{*},p\cdot\varepsilon
p^{*})\mid(w,p)\in C^{\prime}]$

11: Append $C^{\prime\prime}$ to $S$

12:Remove dominated pairs in $S$ and sort the remaining points

13:return $S$

Now we are ready to give the main algorithm. The idea is the same as in the
FPTAS in Algorithm 4, except that we replace the MaxConv computations, i.e.,
we use Lemma 28 instead of Lemma 24. We will use the following notation. Given
a sequence $A[0,\dots,n]$, and an integer $i\geq 1$ we denote by
$(A[0,\dots,n])^{i}$ the result of applying $2^{i}$ $(\max,+)$-convolutions of
$A$ with itself, i.e.

$(A[0,\dots,n])^{i}:=\underbrace{A[0,\dots,n]\oplus\dots\oplus
A[0,\dots,n]}_{2^{i}\text{ times}}.$

If $i=0$, we set $(A[0,\dots,n])^{0}:=A[0,\dots,n]$. Note that the length of
the resulting sequence is $2^{i}\cdot n$.

Algorithm 6 $\textsc{Weak-FPTAS}(\mathcal{I},W)$: Given an instance
$(\mathcal{I},W)$ of Unbounded Knapsack, the algorithm returns a weak
$(1+O(\varepsilon))$-approximation of
$(\mathcal{P}_{\mathcal{I},0}[0,\dots,W])^{\lceil\log 1/\varepsilon\rceil}$

1:Initialize $S_{0}:=\mathcal{P}_{0}[0,\dots,W]$, stored implicitly

2:for $i=1,\dots,\lceil\log 1/\varepsilon\rceil$ do

3: Approximate $S_{i}:=S_{i-1}\oplus S_{i-1}$ using Lemma 28 with error
parameter $\varepsilon^{\prime}:=\varepsilon/\log(1/\varepsilon)$

4:return $S_{\lceil\log 1/\varepsilon\rceil}$

######  Lemma 29.

Let $(\mathcal{I},W)$ be an instance of Unbounded Knapsack on $n$ items with
$p_{\min}>\varepsilon\mathrm{OPT}$ and $w_{\min}>\varepsilon W$. Then, on
input $(\mathcal{I},W)$ Algorithm 6 computes a weak
$(1+O(\varepsilon))$-approximation of
$(\mathcal{P}_{0}[0,\dots,W])^{\lceil\log 1/\varepsilon\rceil}$ in time
$\widetilde{O}(n+T(1/\varepsilon))$, where $T(n)$ is the time needed to
compute BMMaxConv on length-$n$ sequences.

  * Proof.

First we argue correctness. We will show by induction that for every $i\geq 0$
it holds that $S_{i}$ is a weak $(1+\varepsilon^{\prime})^{i}$-approximation
of $(\mathcal{P}_{0}[0\dots,W])^{i}$. For the base case $i=0$, this holds by
definition of $S_{0}$. For the inductive step, take $i>0$ and assume the claim
holds for $i-1$. By the computation in line 3 of Algorithm 6, $S_{i}$ weakly
$(1+\varepsilon^{\prime})$-approximates $S_{i-1}\oplus S_{i-1}$. And by the
inductive hypothesis, $S_{i-1}$ is a weak
$(1+\varepsilon^{\prime})^{i-1}$-approximation of
$(\mathcal{P}_{0}[0,\dots,W])^{i-1}$. Therefore, by Lemma 27 it follows that
$S_{i}$ weakly $(1+\varepsilon^{\prime})^{i}$-approximates
$(\mathcal{P}_{0}[0,\dots,W])^{i-1}\oplus(\mathcal{P}_{0}[0,\dots,W])^{i-1}=(\mathcal{P}_{0}[0,\dots,W])^{i}$.
Since $\varepsilon^{\prime}=\varepsilon/\log(1/\varepsilon)$, we conclude that
$S_{\lceil\log 1/\varepsilon\rceil}$ is a weak
$(1+\varepsilon^{\prime})^{i}=(1+O(\varepsilon))$-approximation of
$(\mathcal{P}_{0}[0,\dots,W])^{\lceil\log 1/\varepsilon\rceil}$, as desired.

Now we analyze the running time. The initialization in line 1 takes time
$O(n)$. Then, in each iteration of the for-loop we apply Lemma 28 to
approximate the $(\max,+)$-convolutions. When $i=1$ the input sequences have
$O(n)$ steps, and we obtain a sequence with
$O(1/\varepsilon\log(p_{\max}/p_{\min})\log(W/w_{\min}))$ steps which
approximates $\mathcal{P}_{0}[0,\dots,W]\oplus\mathcal{P}[0,\dots,W]$.
Continuing inductively, in the $i$-th iteration we approximate the
$(\max,+)$-convolution of sequences with
$O(n+1/\varepsilon\log(2^{i}p_{\max}/p_{\min})\log(2^{i}W/w_{\min}))$ steps.
Since $i\leq O(\log 1/\varepsilon)$, and by assumption
$p_{\min}>\varepsilon\mathrm{OPT}$ and $w_{\min}>\varepsilon W$ it follows
that the number of steps of the input sequences in every iteration are bounded
by $\widetilde{O}(n+1/\varepsilon)$. Therefore, each iteration takes time
$\widetilde{O}(n+T(1/\varepsilon))$ and thus we can bound the overall running
time by

$\sum_{i=1}^{\lceil\log\frac{1}{\varepsilon}\rceil}\widetilde{O}\left(n+\tfrac{1}{\varepsilon}+T(1/\varepsilon)\right)=\widetilde{O}(n+T(1/\varepsilon)).$

Note that here we are using the niceness assumption that
$T(\widetilde{O}(n))=\widetilde{O}(T(n))$ as mentioned in Section 2. ∎

Now we can put things together to prove the main theorem.

  * Proof of Theorem 26.

Given a instance of $(\mathcal{I},W)$ of Unbounded Knapsack, we first
preprocess it with Algorithm 3 and obtain a new instance
$(\mathcal{I}^{\prime},W)$. Then, we run Algorithm 6 on
$(\mathcal{I}^{\prime},W)$ and obtain a sequence $S$. We claim that
$\tilde{p}:=S[\ell]$ where $\ell:=(1+O(\varepsilon))W$ (for a sufficiently
large hidden constant given by the guarantee of Lemma 29) is the profit of a
feasible solution with profit $\tilde{p}\geq\mathrm{OPT}/(1+O(\varepsilon))$
and weight at most $(1+O(\varepsilon))W$, and that we can compute it in the
desired running time.

To see the claim, first note that after the preprocessing, it holds that
$p_{\min}>2\varepsilon P_{0}\geq\varepsilon\mathrm{OPT}$ and
$w_{\min}>\varepsilon W$. Hence, we can apply Lemma 29 and conclude that we
can compute $S$ in the desired running time. To argue about correctness, let
$x^{*}$ be the optimal solution for the original instance $(\mathcal{I},W)$,
i.e., $\mathcal{P}_{\mathcal{I}}[W]=p(x^{*})=\mathrm{OPT}$. By Lemma 23, there
is a solution $\tilde{x}$ from $\mathcal{I}^{\prime}$ which satisfies
$p(\tilde{x})\geq(1-8\varepsilon)p(x^{*})=(1-8\varepsilon)\mathrm{OPT}$ and
$w(\tilde{x})\leq w(x^{*})\leq W$. Thus, it suffices to argue that $S[\ell]$
corresponds to a solution from $\mathcal{I}^{\prime}$ which weakly-
approximates $\tilde{x}$.

Since the maximum number of items in any feasible solution for
$(\mathcal{I}^{\prime},W)$ is at most $W/w_{\min}<1/\varepsilon$, we can apply
Lemma 20 inductively to obtain that

$(\mathcal{P}_{\mathcal{I}^{\prime},0}[0,\dots,W])^{\lceil\log
1/\varepsilon\rceil}[0,\dots,W]=\mathcal{P}_{\mathcal{I}^{\prime}}[0,\dots,W].$
(3)

Now, Lemma 29 guarantees that the output sequence $S$ is a weak
$(1+O(\varepsilon))$-approximation of
$(\mathcal{P}_{\mathcal{I}^{\prime},0}[0,\dots,W])^{\lceil\log
1/\varepsilon\rceil}$. Therefore by combining (3), property (i) of Definition
2 and monotonicity we have that $S_{\lceil\log
1/\varepsilon\rceil}[\ell]\geq\mathrm{OPT}/(1+O(\varepsilon))$. Moreover, by
property (ii) of Definition 2 we know that this indeed corresponds to a
solution from $\mathcal{I}^{\prime}$ of weight at most $(1+O(\varepsilon))W$.
∎

###  Solution Reconstruction

For both our strong and weak approximation schemes presented in Section 5, we
only described how to obtain an approximation of the _value_ of the optimal
solution. We can also reconstruct the solution itself by computing the
witnesses of each $(\max,+)$-convolution (see Appendix B), as we show in the
following lemma.

######  Lemma 30.

A solution attaining the value given by Algorithm 6 can be found in time
$\widetilde{O}(n+T(1/\varepsilon))$, where $T(n)$ is the time to compute
BMMaxConv on length-$n$ sequences.

  * Proof Sketch.

We run Algorithm 6, but additionally compute witnesses for each convolution.
More precisely, consider the sequence $S_{i}$ obtained at each iteration $i$
of Algorithm 6. Note that via Lemma 9 we can obtain the witness array for
every step in $S_{i}$ by computing the witnesses of each
$(\max,+)$-convolution computed inside Lemma 28, which only adds a
polylogarithmic overhead to the running time. After doing this, for every step
in $S_{i}$ we can obtain the corresponding two steps in $S_{i-1}$ that define
it in constant time (by doing a lookup in the witness arrays). Thus, to
reconstruct the optimal solution we proceed by obtaining the steps which
define the solution $S_{\lceil\log 1/\varepsilon\rceil}[(1+O(\varepsilon))W]$,
and recursively find the steps which define them in the previous level.
Proceeding in this way, we eventually hit the entries of $\mathcal{P}_{0}$,
which correspond to the items from $\mathcal{I}^{\prime}$ which correspond to
the solution found. The correctness of this procedure follows simply because
we trace back the computation which led to the output value and store the
items found in the first level. Since we can lookup the witnesses in constant
time and at the $i$-th level of recursion we have $2^{i}$ subproblems, the
running time is $O(\sum_{i\leq\log 1/\varepsilon}2^{i})=O(1/\varepsilon)$. ∎

With an analogous proof we can show the same for the strong FPTAS:

######  Lemma 31.

A solution attaining the value given by Algorithm 4 can be found in time
$\widetilde{O}(n+T(1/\varepsilon))$, where $T(n)$ is the time to compute
MaxConv on length-$n$ sequences.

##  Hardness Results

In this section we establish a reduction from BMMaxConv to Unbounded Knapsack.
By combining this with our algorithms in previous sections, we establish an
equivalence between BMMaxConv and various 0-1 Knapsack problems.

###  Retracing known reductions

We follow the reduction from MaxConv to Unbounded Knapsack of [CMWW19] and
[KPS17], but starting from BMMaxConv instead of general instances. In
particular, we closely follow the structure of Cygan et al.’s proof. Their
reduction proceeds in three steps using the following intermediate problems.
Note that we define the bounded monotone (BM) versions of their problems.

BMMaxConv UpperBound Input: Monotone non-decreasing sequences
$A[0,\dots,n],B[0,\dots,n],C[0,\dots,2n]$ with entries in $[O(n)]$ Task:
Decide whether for all $k\in[2n]$ we have $C[k]\geq\max_{i+j=k}A[i]+B[j]$

BMSuperAdditivity Testing Input: A monotone non-decreasing sequence
$A[0,\dots,n]$ where each $A[i]\in[O(n)]$ for all $i\in[n]$ Task: Decide
whether for all $k\in[n]$ we have $A[k]\geq\max_{i+j=k}A[i]+A[j]$

The first step is to reduce BMMaxConv to its decision version BMMaxConv
UpperBound. The technique used in this step traces back to a reduction from
$(\min,+)$-matrix product to negative weight triangle detection in graphs due
to Vassilevska Williams and Williams [VWW18]. Our proof is very similar to
[CMWW19, Theorem 5.5], but we need some extra care to ensure that the
constructed instances have bounded entries.

######  Proposition 32.

Given an algorithm for BMMaxConv UpperBound in time $T(n)$, we can _find_ a
violated constraint $C[i+j]<A[i]+B[j]$ if it exists in time $O(T(n)\cdot\log
n)$.

  * Proof.

Suppose $A,B,C$ form a NO-instance of BMMaxConv UpperBound and let
$k^{*}=i^{*}+j^{*}$ be the smallest index for which we have a violated
constraint $C[k^{*}]<A[i^{*}]+B[j^{*}]$. Note that for any $k<k^{*}$ the
prefixes $A[0,\dots,k],B[0,\dots,k],C[0,\dots,k]$ form a YES instance of
BMMaxConv UpperBound. Thus, we can do binary search over prefixes to find
$k^{*}$. ∎

######  Lemma 33 ($\text{{BMMaxConv}}{}\rightarrow\text{{BMMaxConv
UpperBound}}{}$).

If BMMaxConv UpperBound can be solved in time $T(n)$, then BMMaxConv can be
solved in time $\widetilde{O}(n\cdot T(\sqrt{n}))$.

  * Proof.

Let $A[0,\dots,n],B[0,\dots,n]$ be an input instance of BMMaxConv. We will
describe a procedure which given a sequence $C$ of length $2n+1$, outputs for
each $k\in[2n]$ whether $C[k]\geq\max_{i+j=k}A[i]+B[j]$. Given this procedure,
we can determine all entries of $A\oplus B$ by a simultaneous binary search
using $C$ in $O(\log n)$ calls. Since $A,B$ are monotone non-decreasing, the
sequence of guessed values $C$ will remain monotone in all iterations.

We split the input sequences of BMMaxConv as follows. Let $\Delta=O(n)$ be the
largest value in $A$ and $B$. Given an interval $I\subseteq[n]$, we denote by
$A_{I}$ the contiguous subsequence of $A$ indexed by $I$. Among the indices
$i\in[n]$, we mark every multiple of $\lceil\sqrt{n}\rceil$. We also mark the
smallest index $i$ with $A[i]\geq j\cdot\lceil\sqrt{\Delta}\rceil$, for every
integer $1\leq j\leq\sqrt{\Delta}$. Then we split $A$ at every marked index,
obtaining subsequences $A_{I_{0}},\ldots,A_{I_{a}}$ for $a\leq
n^{\prime}:=\lceil\sqrt{n}\rceil+\lceil\sqrt{\Delta}\rceil$. We analogously
construct intervals $J_{0},\dots,J_{b}$ with $b\leq n^{\prime}$ which
partition $B$.

Let $C[0,\dots,2n]$ be the sequence which we use to binary search the values
of $A\oplus B$. Recall that our goal is to determine for each $k$ whether
$C[k]\geq\max_{i+j=k}A[i]+B[j]$. We will describe an iterative procedure which
returns a binary array $M[0,\dots,2n]$ where $M[k]=1$ if we have determined
that $C[k]<\max_{i+j=k}A[i]+B[j]$, and $M[k]=0$ otherwise.

Initialize $M[k]=0$ for all $k\in[2n]$. Iterate over each
$(x,y)\in[a]\times[b]$. We now describe how to check if $A[i]+B[j]\leq C[i+j]$
holds for all $i\in I_{x}$ and $j\in I_{y}$, or otherwise find a violated
constraint using the oracle for BMMaxConv UpperBound. Let $L:=\min
A_{I_{x}}+\min B_{J_{y}}$ and $U:=\max A_{I_{x}}+\max B_{J_{y}}$. We proceed
in the following two steps:

  1. 1.

Identify all indices $k\in I_{x}+I_{y}$ for which $C[k]<L$. Since
$A[i]+B[j]\geq L$ for every $i\in I_{x},j\in J_{y}$, we conclude that
$C[k]<\max_{i+j=k}A[i]+B[j]$, and thus set $M[k]=1$ for every such index.

  2. 2.

Add extra dummy entries $C[2n+1]:=\infty$, and $M[2n+1]=0$. Let
$\mathrm{next}(k):=\min\\{j\mid j\geq k,M[j]=0\\}$. We construct a new
sequence $C^{\prime}$ by setting for every index $k\in I_{x}+I_{y}$:

$C^{\prime}[k]:=\min\\{C[\mathrm{next}(k)],U+1\\}.$

The purpose of the dummy entries is to set $C^{\prime}[k]:=U+1$ if there is no
$k\leq j\leq 2n$ for which $M[j]=0$. Due to the monotonicity of $C$, it
follows that $C^{\prime}$ is also monotone. Further, it holds that $L\leq
C^{\prime}[k]\leq U+1$ for every entry $k$. Intuitively, the purpose of
$\mathrm{next}(k)$ is to ignore the entries which already have been marked
$M[k]=1$ in step 1, or in previous iterations.

Now we want to find a violating index
$C^{\prime}[i+j]<A_{I_{x}}[i]+B_{J_{y}}[j]$ if it exists, using the BMMaxConv
UpperBound oracle. In order to do so, we shift the values of
$A_{I_{x}},B_{J_{y}}$ and $C^{\prime}$ appropriately. More precisely, let
$L_{A}:=\min A_{I_{x}}$ and $L_{B}:=\min B_{J_{y}}$ be the lowest numbers in
$A_{I_{x}},B_{J_{y}}$ respectively. We substract $L_{A}$ from every element in
$A_{I_{x}}$, $L_{B}$ from every element in $B_{J_{y}}$ and $L_{A}+L_{B}$ from
every element in $C^{\prime}$. This makes all entries bounded by
$O(n^{\prime})=O(\sqrt{n})$, and a violating index in the resulting instance
is a violating index before shifting since we substract the same quantity from
both sides of the inequality $C^{\prime}[i+j]<A_{I_{x}}[i]+B_{J_{y}}[j]$.
Thus, we can use Proposition 32 to find a violating index $k=i+j$ if it
exists, and if so, set $M[\mathrm{next}(k)]:=1$.

We repeat step 2 until we find no more violating indices (recomputing the
sequence $C^{\prime}$ in each iteration). Then we repeat the process with the
next pair $(x,y)$.

We claim that in this way, we correctly compute the array of violated indices
$M$. To see correctness, note that step 1 is trivially correct due to the
lower bound on any pair of sums. For step 2, note that if we find a violating
index $k=i+j$ and $\mathrm{next}(k)=k$, then setting $M[k]=1$ is clearly
correct. If $\mathrm{next}(k)\neq k$, it means that we had marked the index
$M[k]=1$ in a previous iteration or in step 1. Due to the monotonicity of
$A,B$ and $C$ and the definition of $z:=\mathrm{next}(k)$, we have that

$C[z]=C^{\prime}[k]=C^{\prime}[i+j]<A[i]+B[j]\leq\max_{i^{\prime}+j^{\prime}=k}A[i^{\prime}]+B[j^{\prime}]\leq\max_{i^{\prime}+j^{\prime}=z}A[i^{\prime}]+B[j^{\prime}],$

so marking $M[z]=1$ is correct. Conversely, for any index $k=i+j$ such that
$C[k]<A[i]+B[j]$ at some iteration we will consider the subsequences where
$i\in I_{x}$ and $j\in I_{y}$ holds. Since we repeat step 2 until no more
violating indices are found, the index $k$ will be marked during some
iteration.

Finally we analyze the running time of the reduction. We consider $O(n)$ pairs
$x,y\in[a]\times[b]$. For each such pair, step 1 takes time
$O(n^{\prime})=O(\sqrt{n})$. We execute step 2 at least once for each pair
$(x,y)$, and in total once for every index that we mark as violated. Since
every index $k$ gets marked at most once, this amounts to $O(n)$ calls to
Proposition 32, which results in $O(n\log n)$ calls to the oracle of BMMaxConv
UpperBound. Each such call takes time $O(T(\sqrt{n}))$. Since we do a
simultaneous binary search over $C$, the overall time of the reduction is
$O(n\cdot T(\sqrt{n})\log^{2}n)$. ∎

The next step is to reduce BMMaxConv UpperBound to BMSuperAdditivity Testing.
The proof is exactly the same as [CMWW19, Theorem 5.4]; we include it for
completeness.

######  Lemma 34 ($\text{{BMMaxConv
UpperBound}}{}\rightarrow\text{{BMSuperAdditivity Testing}}{}$).

If BMSuperAdditivity Testing can be solved in time $T(n)$, then BMMaxConv
UpperBound can be solved in time $O(T(n))$.

  * Proof.

Let $\Delta=O(n)$ be the maximum number in the input sequences $A,B,C$ of
BMMaxConv UpperBound. We construct an equivalent instance $E[0,\dots,4n+3]$ of
BMSuperAdditivity Testing as follows: for each $i\in[n]$ set $E[i]:=0$,
$E[n+1+i]:=\Delta+A[i]$, $E[2n+2+i]:=4\Delta+B[i]$ and
$E[3n+3+i]:=5\Delta+C[i]$. Note that $|E|=O(n)$ and all values are bounded by
$O(\Delta)=O(n)$.

If there are indices $i,j\in[n]$ such that $A[i]+B[j]>C[i+j]$, then
$E[n+1+i]+E[2n+2+j]>E[3n+3+i+j]$, so $E$ is a NO instance. Otherwise, let
$i\leq j$ with $i+j\leq 4n+3$ be any pair of indices. If $i\leq n$, then since
$E[i]=0$ we have $E[i]+E[j]\leq E[i+j]$. So assume $i>n$. If $j\in[n+1,2n+1]$
then $E[i]+E[j]\leq 4\Delta\leq E[i+j]$. Hence, since $i\leq j$ and $i+j\leq
4n+3$ we have that $i\in[n+1,2n+1]$ and $j\in[2n+2,3n+2]$. For these ranges,
the super-additivity of $E$ corresponds exactly to the BMMaxConv UpperBound
condition of $A,B,C$. ∎

Finally, we reduce BMSuperAdditivity Testing to Unbounded Knapsack. The idea
is essentially the same as [CMWW19, Theorem 5.3], but in their proof they
construct instances of Unbounded Knapsack where the maximum profit could be as
large as $p_{\max}=O(n^{2})$; we improve this to $p_{\max}=O(n)$. (More
precisely, the variable $D$ is defined as $D:=\sum_{i}A[i]$ in their proof,
while we show that it is enough to set $D=O(A[n])$.)

######  Lemma 35 ($\text{{BMSuperAdditivity
Testing}}{}\rightarrow\text{{Unbounded Knapsack}}{}$).

There is a linear-time reduction from BMSuperAdditivity Testing on sequences
of length $n$ to an instance of Unbounded Knapsack on $n$ items with
$W,\mathrm{OPT}=O(n)$.

  * Proof.

Let $A[0,\dots,n]$ be an instance of BMSuperAdditivity Testing. We construct
an equivalent instance of Unbounded Knapsack as follows. Set $D:=5\cdot A[n]$
and $W:=2n+1$. For every $i\in[n]$ we create a _light item_ $(A[i],i)$ and a
_heavy item_ $(D-A[i],W-i)$, where the first entry of each item is its profit
and the second is its weight. We set the weight constraint to $W$.

Suppose $A[0,\dots,n]$ is a NO instance. Then, there exist $i,j\in[n]$ such
that $A[i]+A[j]>A[i+j]$. Hence, $(A[i],i),(A[j],j)$ and $(D-A[i+j],W-i-j)$
form a feasible solution for Unbounded Knapsack with weight $W$ and total
profit $A[i]+A[j]+D-A[i+j]\geq D+1$.

On the other hand, suppose we start from a YES instance. Consider any feasible
solution to the Unbounded Knapsack instance. We make two observations. First,
if the solution contains any two light items $(A[i],i)$ and $(A[j],j)$ with
$i+j\leq n$, then since $A$ is a YES instance, we can replace both items by
$(A[i+j],i+j)$ and the profit is at least as good. The second observation is
that any feasible solution can contain at most one heavy item, since every
such item has weight at least $n+1$ and the weight constraint is $W=2n+1$.
Now, suppose that $\mathrm{OPT}$ contains one heavy item of the form
$(D-A[k],W-k)$. By the first observation, the most profitable way of packing
the remaining capacity is to include the item $(A[k],k)$. Thus, in this case,
we have that the value of $\mathrm{OPT}$ is $D-A[k]+A[k]=D$. If $\mathrm{OPT}$
does not contain any heavy item, note that by the first observation it
consists of at most 4 light items. Therefore, its value is at most
$4A[n]<D=5A[n]$. ∎

Putting together the previous lemmas, we obtain the following theorem.

######  Theorem 36.

If Unbounded Knapsack on instances with $n$ items with $W,\mathrm{OPT}=O(n)$
can be solved in time $T(n)$, then BMMaxConv on sequences of length $n$ can be
solved in time $\widetilde{O}(n\cdot T(\sqrt{n}))$.

We will also need the following reduction from Unbounded Knapsack to 0-1
Knapsack from [CMWW19, Theorem 5.1]; we include the proof for completeness.

######  Lemma 37 ($\text{{Unbounded Knapsack}}{}\rightarrow\text{{0-1
Knapsack}}{}$).

If 0-1 Knapsack on instances with $n$ items and $W,\mathrm{OPT}=O(n)$ can be
solved in time $T(n)$, then Unbounded Knapsack on instances with $n$ items and
$W,\mathrm{OPT}=O(n)$ can be solved in time $\widetilde{O}(T(n))$.

  * Proof.

Let $\mathcal{I}=\\{(p_{i},w_{i})\\}_{i\in[n]}$ with capacity $W$ be an
instance of Unbounded Knapsack. We construct an equivalent instance of 0-1
Knapsack with the item set

$\mathcal{I}^{\prime}:=\\{(2^{j}p_{i},2^{j}w_{i})\mid(p_{i},w_{i})\in\mathcal{I},\;0\leq
j\leq\log W\\},$

and the same capacity $W$. Let $x\in\mathbb{N}^{n}$ be a solution of the
Unbounded Knapsack instance $\cal I$, where $x_{i}$ is the multiplicity of
item $(p_{i},w_{i})$. We can construct an equivalent solution
$x^{\prime}\in\\{0,1\\}^{|\mathcal{I}^{\prime}|}$ of the 0-1 Knapsack instance
$\mathcal{I}^{\prime}$ by expressing each $x_{i}\leq W$ in binary and adding
to $x^{\prime}$ the items from $\mathcal{I}^{\prime}$ corresponding to the
non-zero coefficients. In this way,
$w_{\mathcal{I}}(x)=w_{\mathcal{I}^{\prime}}(x^{\prime})$ and
$p_{\mathcal{I}}(x)=p_{\mathcal{I}^{\prime}}(x^{\prime})$. It is easy to see
that this mapping can be inverted, which establishes the equivalence between
the instances.

Note that this reduction does not change $W$ and $\mathrm{OPT}$, and $n$
increases to $n\log W=O(n\log n)$. Thus for Unbounded Knapsack we obtain
running time $O(T(n\log n))=\widetilde{O}(T(n))$. Here we used the niceness
assumption on $T(n)$. ∎

###  Consequences

In this section we combine the reductions from Section 6.1, as well as our
algorithms from Section 5, Section 3, and Section 4, to prove Theorem 5.

We start by showing how a weak approximation for Unbounded Knapsack gives an
exact algorithm for BMMaxConv.

######  Lemma 38 ($\text{{BMMaxConv}}{}\rightarrow\text{Approximate
}\text{{Unbounded Knapsack}}{}$).

If Unbounded Knapsack has a weak approximation scheme running in time
$T(n,\varepsilon)$, then BMMaxConv can be solved in time $O(n\cdot
T(\sqrt{n},1/\sqrt{n}))$.

  * Proof.

Note that a weak approximation scheme for Unbounded Knapsack allows us to
solve instances _exactly_ by setting
$\varepsilon:=\Theta(1/(W+\mathrm{OPT}))$. Since the reduction from Theorem 36
produces $O(n)$ instances of Unbounded Knapsack with $\sqrt{n}$ items and
$W,\mathrm{OPT}=O(\sqrt{n})$, we obtain an algorithm for BMMaxConv by setting
$\varepsilon=\Theta(1/\sqrt{n})$. The overall running time becomes $O(n\cdot
T(\sqrt{n},1/\sqrt{n}))$. ∎

Finally, we put the pieces together to prove Theorem 5, which we restate for
convenience:

See 5

  * Proof.

In the following, we write $A\rightarrow B$ to denote a reduction from problem
$A$ to problem $B$. For every reduction stated in the following list, we
obtain the stronger guarantee that if $B$ can be solved in time
$\widetilde{O}(n^{2-\delta})$, then $A$ can be solved in time
$\widetilde{O}(n^{2-\delta})$, i.e. without any loss in the exponent:

    * $\blacksquare$

$(2)\rightarrow(1)$: Follows from Theorem 10.

    * $\blacksquare$

$(2)\rightarrow(3)$: Follows from Lemma 37.

    * $\blacksquare$

$(3)\rightarrow(1)$: Follows from Theorem 19.

    * $\blacksquare$

$(4)\rightarrow(1)$: Follows from Theorem 26.

For the remaining two reductions below, we obtain the weaker guarantee as
stated in the theorem. Namely, if $B$ can be solved in time
$\widetilde{O}(n^{2-\delta})$, then $A$ can be solved in time
$\widetilde{O}(n^{2-\delta/2})$:

    * $\blacksquare$

$(1)\rightarrow(2)$: Follows from Theorem 36.

    * $\blacksquare$

$(1)\rightarrow(4)$: Follows from Lemma 38.

Finally, note that for any pair of problems $A$ and $B$ in the theorem
statement, we can reduce $A$ to $B$ by chaining the reductions written in the
previous two lists and use at most one reduction which reduces the saving to
$\delta/2$. This guarantees that if $B$ can be solved in time
$\widetilde{O}(n^{2-\delta})$, then $A$ can be solved in time
$\widetilde{O}(n^{2-\delta/2})$, as desired. ∎

## References

  * [AGMN92] Noga Alon, Zvi Galil, Oded Margalit, and Moni Naor.  Witnesses for Boolean matrix multiplication and for shortest paths.  In FOCS, pages 417–426. IEEE Computer Society, 1992.
  * [AN96] Noga Alon and Moni Naor.  Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions.  Algorithmica, 16(4/5):434–449, 1996.
  * [AT19] Kyriakos Axiotis and Christos Tzamos.  Capacitated dynamic programming: Faster Knapsack and graph algorithms.  In ICALP, volume 132 of LIPIcs, pages 19:1–19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [BCD+14] David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian.  Necklaces, convolutions, and X+Y.  Algorithmica, 69(2):294–314, 2014.
  * [Bel57] Richard Bellman.  Dynamic Programming.  Princeton University Press, Princeton, NJ, USA, 1957.
  * [BGSW19] Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams.  Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product.  SIAM J. Comput., 48(2):481–512, 2019.
  * [BHSS18] MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein.  Fast algorithms for Knapsack via convolution and prediction.  In STOC, pages 1269–1282. ACM, 2018.
  * [BHWZ94] Michael R. Bussieck, Hannes Hassler, Gerhard J. Woeginger, and Uwe T. Zimmermann.  Fast algorithms for the maximum convolution problem.  Oper. Res. Lett., 15(3):133–141, 1994.
  * [BIS17] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt.  Better approximations for tree sparsity in nearly-linear time.  In SODA, pages 2215–2229. SIAM, 2017.
  * [BN21] Karl Bringmann and Vasileios Nakos.  A fine-grained perspective on approximating Subset sum and Partition.  In SODA, pages 1797–1815. SIAM, 2021.
  * [Bri17] Karl Bringmann.  A near-linear pseudopolynomial time algorithm for Subset Sum.  In SODA, pages 1073–1084. SIAM, 2017.
  * [BW21] Karl Bringmann and Philip Wellnitz.  On near-linear-time algorithms for dense subset sum.  In SODA, pages 1777–1796. SIAM, 2021.
  * [CDXZ22] Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang.  Faster min-plus product for monotone instances.  In STOC. ACM, 2022.
  * [CH19] Timothy M. Chan and Sariel Har-Peled.  Smallest k-enclosing rectangle revisited.  In SoCG, volume 129 of LIPIcs, pages 23:1–23:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [CH22] Timothy M. Chan and Qizheng He.  More on change-making and related problems.  J. Comput. Syst. Sci., 124:159–169, 2022.
  * [Cha18] Timothy M. Chan.  Approximation schemes for 0-1 Knapsack.  In SOSA, volume 61 of OASICS, pages 5:1–5:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [CL15] Timothy M. Chan and Moshe Lewenstein.  Clustered integer 3SUM via Additive Combinatorics.  In STOC, pages 31–40. ACM, 2015.
  * [CMWW19] Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk.  On problems equivalent to (min, +)-convolution.  ACM Trans. Algorithms, 15(1):14:1–14:25, 2019.
  * [CW21] Timothy M. Chan and R. Ryan Williams.  Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky.  ACM Trans. Algorithms, 17(1):2:1–2:14, 2021.
  * [EW20] Friedrich Eisenbrand and Robert Weismantel.  Proximity results and faster algorithms for integer programming using the Steinitz lemma.  ACM Trans. Algorithms, 16(1):5:1–5:14, 2020.
  * [GM91] Zvi Galil and Oded Margalit.  An almost linear-time algorithm for the dense subset-sum problem.  SIAM J. Comput., 20(6):1157–1189, 1991.
  * [GS80] V. S. Grinberg and S. V. Sevastyanov.  Value of the Steinitz constant.  Funktsional. Anal. i Prilozhen., 14(2):56–57, 1980.
  * [IK75] Oscar H. Ibarra and Chul E. Kim.  Fast approximation algorithms for the Knapsack and Sum of Subset problems.  J. ACM, 22(4):463–468, 1975.
  * [JK18] Klaus Jansen and Stefan Erich Julius Kraft.  A faster FPTAS for the Unbounded Knapsack problem.  Eur. J. Comb., 68:148–174, 2018.
  * [JR19] Klaus Jansen and Lars Rohwedder.  On integer programming and convolution.  In ITCS, volume 124 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [JW19] Ce Jin and Hongxun Wu.  A simple near-linear pseudopolynomial time randomized algorithm for Subset Sum.  In SOSA, volume 69 of OASICS, pages 17:1–17:6. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [KP04] Hans Kellerer and Ulrich Pferschy.  Improved dynamic programming in connection with an FPTAS for the knapsack problem.  J. Comb. Optim., 8(1):5–11, 2004.
  * [KPS17] Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider.  On the fine-grained complexity of one-dimensional dynamic programming.  In ICALP, volume 80 of LIPIcs, pages 21:1–21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [Law79] Eugene L. Lawler.  Fast approximation algorithms for Knapsack problems.  Math. Oper. Res., 4(4):339–356, 1979.
  * [LRC14] Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese.  On lower bounds for the maximum consecutive subsums problem and the (min, +)-convolution.  In ISIT, pages 1807–1811. IEEE, 2014.
  * [Mat10] Jiří Matoušek.  Thirty-three miniatures: Mathematical and Algorithmic applications of Linear Algebra.  American Mathematical Society Providence, RI, 2010.
  * [MWW19] Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk.  A subquadratic approximation scheme for Partition.  In SODA, pages 70–88. SIAM, 2019.
  * [Pis99] David Pisinger.  Linear time algorithms for Knapsack problems with bounded weights.  J. Algorithms, 33(1):1–14, 1999.
  * [PRW21] Adam Polak, Lars Rohwedder, and Karol Wegrzycki.  Knapsack and Subset Sum with small items.  In ICALP, volume 198 of LIPIcs, pages 106:1–106:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [Sei95] Raimund Seidel.  On the All-Pairs-Shortest-Path problem in unweighted undirected graphs.  J. Comput. Syst. Sci., 51(3):400–403, 1995.
  * [Ste13] Ernst Steinitz.  Bedingt konvergente Reihen und konvexe Systeme.  Journal für die reine und angewandte Mathematik, 143:128–176, 1913\.
  * [VWW18] Virginia Vassilevska Williams and R. Ryan Williams.  Subcubic equivalences between path, matrix, and triangle problems.  J. ACM, 65(5):27:1–27:38, 2018.
  * [Wil18] R. Ryan Williams.  Faster All-Pairs Shortest Paths via circuit complexity.  SIAM J. Comput., 47(5):1965–1985, 2018.

##  Appendix A Missing Proofs from Section 2

  * Proof of Proposition 7.

By shifting the indices, we can assume that $A[I]$ and $B[J]$ are sequences
$A^{\prime}[0,\dots,|I|-1]$ and $B^{\prime}[0,\dots,|J|-1]$. Compute
$C^{\prime}:=A^{\prime}\oplus B^{\prime}$ in time $T(|A|+|B|)$. By shifting
the indices back, we can infer the values of the entries $C[I+J]=A[I]\oplus
B[J]$. Thus, we can simply read off the entries in $C[K]$ from the array
$C^{\prime}$. ∎

##### Equivalence between variants of BMMaxConv

As stated in Section 2, the algorithm of Chi, Duan, Xie and Zhang [CDXZ22]
computes the $(\min,+)$-convolution of sequences which are monotone increasing
and have values in $[O(n)]$. The following proposition shows that this is
equivalent to solving MaxConv on monotone non-decreasing sequences with values
in $[O(n)]\cup\\{-\infty\\}$, which justifies Theorem 8.

######  Proposition 39.

MaxConv on monotone non-decreasing sequences of length $n$ and values in
$[O(n)]\cup\\{-\infty\\}$ is equivalent to MinConv on monotone increasing
sequences of length $n$ and values in $[O(n)]$, in the sense that if one can
be solved in time $T(n)$ then the other can be solved in time $O(T(n))$.

  * Proof.

We first describe how to reduce MaxConv on monotone non-decreasing sequences
and values in $[O(n)]\cup\\{-\infty\\}$ to MinConv on monotone increasing
sequences and values in $[O(n)]$ via a simple chain of reductions:

    * $\blacksquare$

_Removing $-\infty$:_ Let $A[0,\dots,n],B[0,\dots,n]$ be an instance of
MaxConv where $A,B$ are monotone non-decreasing and
$A[i],B[i]\in[O(n)]\cup\\{-\infty\\}$. We start by reducing it to an
equivalent instance of MaxConv on monotone non-decreasing sequences and values
in $[O(n)]$ (i.e. we remove the $-\infty$ entries). Let $\Delta$ be the
maximum entry of $A$ and $B$. Construct a new sequence $A^{\prime}[0,\dots,n]$
where $A^{\prime}[i]:=0$ if $A[i]=-\infty$, and $A^{\prime}[i]:=A[i]+2\Delta$
otherwise. Construct $B^{\prime}[0,\dots,n]$ from $B$ in the same way. Note
that $A^{\prime}$ and $B^{\prime}$ are monotone non-decreasing and have values
in $[O(n)]$. Moreover, we can infer the values of any entry $(A\oplus B)[k]$
from $C^{\prime}$: if $C^{\prime}[k]\leq 3\Delta$ then $(A\oplus
B)[k]=-\infty$ and otherwise $(A\oplus B)[k]=C^{\prime}[k]-4\Delta$.

    * $\blacksquare$

_Reducing to MaxConv on non-increasing sequences:_ Now we reduce an instance
$A[0,\dots,n]$, $B[0,\dots,n]$ of MaxConv on monotone non-decreasing sequences
and values in $[O(n)]$ to an instance of MinConv on monotone non-increasing
sequences and values in $[O(n)]$. Let $\Delta$ be the maximum entry of $A$ and
$B$. Construct two new sequences $A^{\prime}$ and $B^{\prime}$ by setting
$A^{\prime}[i]:=\Delta-A[i]$ and $B^{\prime}[i]:=\Delta-B[i]$. Then
$A^{\prime}$ and $B^{\prime}$ are monotone non-increasing and given their
$(\min,+)$-convolution we can easily infer the $(\max,+)$-convolution of $A$
and $B$.

    * $\blacksquare$

_Reducing to MinConv on increasing sequences:_ Next, we reduce an instance
$A[0,\dots,n]$, $B[0,\dots,n]$ of MinConv on monotone non-increasing sequences
and values in $[O(n)]$ to an instance of MinConv on increasing sequences and
values in $[O(n)]$. Construct two new sequences $A^{\prime}$ and $B^{\prime}$
by reversing and adding a linear function to $A$ and $B$, i.e., set
$A^{\prime}[i]:=A[n-i]+i$ and $B^{\prime}[i]:=B[n-i]+i$ for every $i\in[n]$.
Note that $A^{\prime}$ and $B^{\prime}$ are monotone increasing sequences, and
given their $(\min,+)$-convolution we can infer the $(\min,+)$-convolution of
$A$ and $B$.

Combining the reductions above, we conclude that MaxConv on monotone non-
decreasing sequences with values in $[O(n)]\cup\\{-\infty\\}$ can be reduced
in linear time to MinConv on monotone increasing sequences with values in
$[O(n)]$. To show the reduction in the other direction, we can apply the same
ideas: we first negate the entries and shift them to make them non-negative,
then reverse the resulting sequences. We omit the details. ∎

##  Appendix B Witnesses for BMMaxConv

In this section we give the proof of Lemma 9. For the remainder of this
section, fix an instance $A[0,\dots,n],B[0,\dots,n]$ of BMMaxConv and let
$C:=A\oplus B$. To compute the witness array $M[0,\dots,2n]$, we first show