]}

#  $(1-\varepsilon)$-Approximation of Knapsack in Nearly Quadratic Time

Xiao Mao
Stanford University
<EMAIL_ADDRESS>

###### Abstract

_Knapsack_ is one of the most fundamental problems in theoretical computer
science. In the $(1-\varepsilon)$-approximation setting, although there is a
fine-grained lower bound of $(n+1/\varepsilon)^{2-o(1)}$ based on the
$(\min,+)$-convolution hypothesis ([Künnemann, Paturi and Stefan Schneider,
ICALP 2017] and [Cygan, Mucha, Wegrzycki and Wlodarczyk, 2017]), the best
algorithm is randomized and runs in
$\tilde{O}\left(n+(\frac{1}{\varepsilon})^{11/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})}\right)$111Throughout
this paper, we use $\tilde{O}(f)$ to denote
$O(f\cdot\text{poly}\log(n/\varepsilon))$.  time [Deng, Jin and Mao, SODA
2023], and it remains an important open problem whether an algorithm with a
running time that matches the lower bound (up to a sub-polynomial factor)
exists. We answer the question positively by showing a deterministic
$(1-\varepsilon)$-approximation scheme for knapsack that runs in
$\tilde{O}(n+(1/\varepsilon)^{2})$ time. We first extend a known lemma in a
recursive way to reduce the problem to $n\varepsilon$-additive approximation
for $n$ items with profits in $[1,2)$. Then we give a simple efficient
geometry-based algorithm for the reduced problem.

##  1 Introduction

_Knapsack_ is one of the most fundamental problems in computer science and
mathematical optimization, and is actively being studied in fields such as
integer programming and fine-grained complexity. In the Knapsack problem
(sometimes also called 0-1 Knapsack), we are given a set $I$ of $n$ items
where each item $i\in I$ has weight $w_{i}>0$ and profit $p_{i}>0$, as well as
a knapsack capacity $W$, and we want to choose a subset $J\subseteq I$
satisfying the weight constraint $\sum_{j\in J}w_{j}\leq W$ such that the
total profit $\sum_{j\in J}p_{j}$ is maximized.

Knapsack is well-known to be hard: it appeared in Karp’s original list of 21
NP-hard problems [Kar72]. To cope with NP-hardness, a natural direction is to
study its _approximation algorithms_. Given a parameter $\varepsilon>0$, and
an input instance with optimal value $\mathrm{OPT}$, a
$(1-\varepsilon)$-approximation algorithm is required to output a number
$\mathrm{SOL}$ such that
$(1-\varepsilon)\mathrm{OPT}\leq\mathrm{SOL}\leq\mathrm{OPT}$. Fortunately,
Knapsack is well-known to have _fully polynomial-time approximation schemes
(FPTASes)_ , namely $(1-\varepsilon)$-approximation algorithm that runs in
$\operatorname{\mathrm{poly}}(n,1/\varepsilon)$ time, for any $\varepsilon>0$.

Table 1: FPTASes for 0-1 knapsack $O\left(n\log n+(\frac{1}{\varepsilon})^{4}\log\frac{1}{\varepsilon}\right)$ | Ibarra and Kim [IK75] | 1975
---|---|---
$O\left(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{4}\right)$ | Lawler [Law79] | 1979
$O\left(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{3}\log^{2}\frac{1}{\varepsilon}\right)$ | Kellerer and Pferschy [KP04] | 2004
$O\left(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{5/2}\log^{3}\frac{1}{\varepsilon}\right)$ (randomized) | Rhee [Rhe15] | 2015
$O\left(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{12/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})}\right)$ | Chan [Cha18] | 2018
$O\left(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{9/4}/2^{\Omega(\sqrt{\log(1/\varepsilon)})}\right)$ | Jin [Jin19] | 2019
$O\left(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{11/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})}\right)$ (randomized) | Deng, Jin and Mao [DJM23] | 2023
$\tilde{O}(n+(\frac{1}{\varepsilon})^{2})$ | This work |

Reductions showed by Cygan et al. [CMWW19] and Künnemann et al. [KPS17] imply
that 0-1 knapsack and unbounded knapsack have no FPTAS in
$O((n+\frac{1}{\varepsilon})^{2-\delta})$ time, unless $(\min,+)$-convolution
admits a truly subquadratic algorithm [MWW19]. Experts in this field have been
in pursuit of an algorithm that matches this lower bound long before such a
lower bound is known. The history of FPTASes for the Knapsack problem is
summarized in Table 1. The first algorithm with only subcubic dependence on
$1/\varepsilon$ was due to Rhee [Rhe15], which reduced the problem to a linear
programming instance that can be solved using special randomized methods. In
2018, Chan [Cha18] gave an elegant algorithm for the 0-1 knapsack problem in
deterministic
$O(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{5/2}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$
via simple combination of the SMAWK algorithm [AKM+87] and a standard divide-
and-conquer technique. The speedup of superpolylogarithmic factor
$2^{\Omega(\sqrt{\log(1/\varepsilon)})}$ was due to progress on
$(\min,+)$-convolution [BCD+14, Wil14, CW16]. Using an elementary number-
theoretic lemma, Chan further improved the algorithm to
$O(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{12/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$
time. Jin extended this algorithm by using a greedy lemma and extending the
number theoretical lemma to multiple layers, obtaining a running time of
$O(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{9/4}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$
[Jin19]. Very recently, Deng, Jin and Mao designed an algorithm that used an
improved greedy lemma using a result in additive combinatorics, as well as a
procedure based on random partitioning, obtaining a running time of
$O(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{11/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$,
but the algorithm was randomized. In this work, we obtain a running time of
$\tilde{O}(n+(1/\varepsilon)^{2})$ deterministically, putting an end to this
decades-long effort to match the lower bound. Although our work uses somewhat
complicated results from previous work as black boxes at the beginning, our
core geometry-based procedure is fairly simple and is quite different from the
framework of techniques made popular by Chan.

For the related unbounded knapsack problem, where every item has infinitely
many copies, Jansen and Kraft [JK18] obtained an
$O(n+(\frac{1}{\varepsilon})^{2}\log^{3}\frac{1}{\varepsilon})$-time
algorithm; the unbounded version can be reduced to 0-1 knapsack with only a
logarithmic blowup in the problem size [CMWW19].

There are also some recent advances for the related problems Subset Sum and
Partition. The Subset Sum problem is a special case of Knapsack, where the
weight of an item is always equal to its profit. The partition problem is an
interesting special case of the Subset Sum problem where
$W=\frac{1}{2}\sum_{i\in I}w_{i}$. For Subset Sum, the best known algorithm by
Bringmann and Nakos [BN21] runs in
$\tilde{O}(n+\varepsilon^{-2}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$ time
(improving [KMPS03] by low-order factors). Bringmann and Nakos [BN21] showed a
matching lower bound based on the $(\min,+)$-convolution hypothesis. For
Partition, the best FPTAS by Deng, Jin and Mao runs in
$\tilde{O}(n+(\frac{1}{\varepsilon})^{5/4})$ time [DJM23]. Abboud, Bringmann,
Hermelin, and Shabtay [ABHS19] showed that Partition cannot be approximated in
$\operatorname{\mathrm{poly}}(n)/\varepsilon^{1-\delta}$ time for any
$\delta>0$, under the Strong Exponential Time Hypothesis.

We can see that before this work, the complexity of Subset Sum is already
settled, but for Knapsack and Partition there still remain gaps between the
best-known algorithm and its conditional lower bound. As we have mentioned, in
this paper, we make a breakthrough that closes this gap for the Knapsack
problem:

######  Theorem 1.1.

There is a deterministic algorithm for $(1-\varepsilon)$-approximating
Knapsack with running time $\tilde{O}(n+\varepsilon^{-2})$.

##  2 Preliminaries

We write $\mathbb{N}=\\{0,1,2,\dots\\}$ and $\mathbb{N}^{+}=\\{1,2,\dots\\}$.
For $n\in\mathbb{N}$ we write $[n]=\\{1,2,\dots,n\\}$. For a finite set $S$ we
let $\left\lvert S\right\rvert$ be the size of $S$ (i.e. the number of
elements in $S$). For a sequence $A=\\{a_{i}\\}$, we let $\left\lvert
A\right\rvert$ be the length of $A$ and for an interval
$[l,r]\in[1,\left\lvert A\right\rvert]$ we write $A_{l,r}$ as a shorthand for
the subsequence $\\{a_{l},a_{l+1},\cdots,a_{r}\\}$.

###  2.1 Problem Statements

In the Knapsack problem, the input is a list of $n$ items
$(p_{1},w_{1}),\dots,(p_{n},w_{n})\in\mathbb{N}\times\mathbb{N}$ together with
a knapsack capacity $W\in\mathbb{N}$, and the optimal value is

$\mathrm{OPT}:=\max_{J\subseteq[n]}\Big{\\{}\sum_{j\in
J}p_{j}\,\Big{|}\,\sum_{j\in J}w_{j}\leq W\Big{\\}}.$

Given a Knapsack instance and a parameter $\varepsilon\in(0,1)$, an
_$(1-\varepsilon)$ -approximation algorithm_ is required to output a number
$\mathrm{SOL}$ such that
$(1-\varepsilon)\mathrm{OPT}\leq\mathrm{SOL}\leq\mathrm{OPT}$.

In this problem, we can assume $n=O(\varepsilon^{-4})$ and hence $\log
n=O(\log\varepsilon^{-1})$. For larger $n$, Lawler’s algorithm [Law79] for
Knapsack in $O(n\log\frac{1}{\varepsilon}+(\frac{1}{\varepsilon})^{4})$ time
is already near-optimal.

We will sometimes describe algorithms with approximation ratio
$1-O(\varepsilon)$ (or $1-\tilde{O}(\varepsilon)$), which can be made
$1-\varepsilon$ by scaling down $\varepsilon$ by a constant factor (or a
logarithmic factor) at the beginning.

###  2.2 Knapsack Problem and Profit functions

In the knapsack problem, assume $0<w_{i}\leq W$ and $p_{i}>0$ for every item
$i$. Then a trivial lower bound of the maximum total profit is
$\max_{j}p_{j}$. At the beginning, we can discard all items $i$ with
$p_{i}\leq\frac{\varepsilon}{n}\max_{j}p_{j}$, reducing the total profit by at
most $\varepsilon\max_{j}p_{j}$, which is only an $O(\varepsilon)$ fraction of
the optimal total profit. Therefore, we can assume
$\frac{\max_{j}p_{j}}{\min_{j}p_{j}}\leq\frac{n}{\varepsilon}$.

We adopt the terminology of Chan [Cha18] with some modification. We use the
term _profit function_ to refer to any monotone non-decreasing step function
over some domain range $x\in[l,r]$. The complexity of a monotone step function
refers to the number of its steps. The $(\max,+)$-convolution of two functions
$f$ with domain $x\in[l_{f},r_{f}]$ and $g$ with domain $x\in[l_{g},r_{g}]$ is
a function with domain $x\in[l_{f}+l_{g},r_{f}+r_{g}]$ and is defined to be:

$(f\oplus
g)(x)=\max_{x_{f}\in[l_{f},r_{f}],x_{g}\in[l_{g},r_{g}],x_{f}+x_{g}=x}f(x_{f})+g(x_{g}).$

The contour of a profit function with domain $x\in[x_{1},x_{k}]$ can be
described by a set $P(f)$ of $(2k-1)$ 2-D points

$\\{(x_{1},y_{1}),(x_{2},y_{1}),(x_{2},y_{2}),(x_{3},y_{2}),\cdots,(x_{k},y_{k-1}),(x_{k},y_{k})\\}$

with $x_{1}<x_{2}<\cdots<x_{k}$ and $y_{1}<y_{2}<\cdots<y_{k}$, where
$f(x)=y_{i}$ for $x_{i}\leq x<x_{i+1}(1\leq i\leq n)$.

For a set $I$ of items, we use $f_{I}$ to denote the profit function defined
as:

$f_{I}(x)=\max\Bigg{\\{}\sum_{i\in J}p_{i}:\sum_{i\in J}w_{i}\leq
x,\;\;J\subseteq I\Bigg{\\}}$

over $x\in[0,+\infty)$.

Let $I_{1},I_{2}$ be two disjoint subsets of items, and $I=I_{1}\cup I_{2}$.
It is straightforward to see that $f_{I}=f_{I_{1}}\oplus f_{I_{2}}$.

For each item $i\in I$, we let its _unit profit_ be $p_{i}/w_{i}$.

###  2.3 $(1-\delta,\Delta)$ approximation up to $t$

We sometimes uses the notion of _$(1-\delta,\Delta)$ -approximation up to
$t$_, as stated below.

######  Definition 2.1 (Approximation for Profit Functions).

For functions $\tilde{f},f$ with identical domains and real numbers
$t,\Delta\in\mathbb{R}_{\geq 0},\delta\in[0,1)$, we say that $\tilde{f}$ is a
_$(1-\delta,\Delta)$ approximation of $f$ up to $t$_, if for all $x$ in their
domain,

$\tilde{f}(x)\leq f(x)$

holds, and

$\tilde{f}(x)\geq(1-\delta)f(x)-\Delta$

holds whenever $f(x)\leq t$.

For the case of $t=+\infty$, we simply omit the phrase “up to $t$.”

We also refer to $(1,\Delta)$ approximation as _$\Delta$ -additive
approximation_, and refer to $(1-\delta,0)$ approximation as _$(1-\delta)$
-multiplicative approximation_, or simply _$(1-\delta)$ approximation_.

We now prove the following fact:

######  Proposition 2.2.

Let $I_{1},I_{2}$ be two disjoint subsets of items. For $i\in\\{1,2\\}$,
suppose $\tilde{f}_{i}$ is a $(1-\delta,\Delta_{i})$ approximation of the
profit function $f_{I_{i}}$ up to $t$. Then,
$f=\tilde{f}_{1}\oplus\tilde{f}_{2}$ is a $(1-\delta,\Delta_{1}+\Delta_{2})$
approximation of $f_{I_{1}\cup I_{2}}$ up to $t$.

###### Proof.

For any $b\in[0,t]$ where $f(b)=f_{1}(b_{1})+f_{2}(b_{2})$ for $b_{1}+b_{2}=b$
and $b_{1},b_{2}\in[0,t]$, we have for $i\in[1,2]$,
$(1-\delta)f_{i}(b_{i})-\Delta_{i}\leq f_{I_{i}}(b_{i})$. Since $I_{1}$ and
$I_{2}$ are disjoint, $f_{I_{1}\cup I_{2}}(b)\geq
f_{I_{1}}(b_{1})+f_{I_{2}}(b_{2})$. Hence,
$f_{I_{1}}(b_{1})+f_{I_{2}}(b_{2})\leq(1-\delta)f_{1}(b_{1})-\Delta_{1}+(1-\delta)f_{2}(b_{2})-\Delta_{2}=(1-\delta)(f_{1}(b_{1})+f_{2}(b_{2}))-(\Delta_{1}+\Delta_{2})=(1-\Delta)f(b)-(\Delta_{1}+\Delta_{2})$.

The converse direction can be verified similarly. ∎

Following Chan [Cha18] and Jin [Jin19], given a monotone step function $f$
with range contained in $\\{-\infty,0\\}\cup[A,B]$, one can round the positive
values of $f$ down to powers of $1/(1-\varepsilon)$, and obtain another profit
function $\tilde{f}$ which has complexity only $O(\varepsilon^{-1}\log(B/A))$,
and $(1-\varepsilon)$-approximates $f$. In our algorithm we will always have
$B/A\leq\operatorname{\mathrm{poly}}(n/\varepsilon)$, so we may always assume
that the intermediate profit functions computed during our algorithm are
monotone step functions with complexity $\tilde{O}(\varepsilon^{-1})$ after
rounding.

###  2.4 Technical Overview

We will first reduce our problem of approximating Knapsack to the case where
we only have a few items (Section 4.1). Namely, we reduce our problem to the
following problem:

######  Problem 1.

Given a list $I$ of $n=O(1/\varepsilon)$ items with $p_{i}$ being multiples of
$\varepsilon$ in interval $[1,2)$222The input profit values in the Knapsack
problem are integers, but in intermediate problems, the profits can be real
numbers due to rounding., compute a profit function that
$(n\varepsilon)$-additively approximates $f_{I}$.

######  Lemma 2.3.

1 can be solved in $\tilde{O}(\varepsilon^{-2})$ time.

The reduction is based on an extension of the Greedy Exchange Lemma in
[DJM23], which reduces the computation to three parts. We observe that one of
the parts is identical to the original problem on a smaller scale, and thus we
can apply the Greedy Exchange Lemma recursively.

The proof of Lemma 2.3 is the crux of our algorithm (Section 4.2). Recall that
profit functions can be described by a series of points. We will show that one
can remove some of these points, obtain a new profit function described by
these points, and still not lose too much precision (Definition 4.3).
Moreover, our point removal scheme guarantees that the remaining points
consist of few blocks of upper or lower convex hulls, and merging profit
functions determined by these points can be done more efficiently (4.4).
Readers can compare these ideas with the ideas based on “sparsification”
described in Bringmann and Nako’s FPTAS for Subset Sum [BN21], which are much
simpler analogs of our ideas in 1D.

##  3 Summary of Previous Techniques

###  3.1 Known Lemmas

By known reductions (e.g., [Cha18, Jin19, DJM23]), we can focus on solving the
following cleaner problem, which already captures the main difficulty of
knapsack:

######  Problem 2.

Assume $\varepsilon\in(0,1/2)$ and $1/\varepsilon\in\mathbb{N}^{+}$. Given a
list $I$ of items $(p_{1},w_{1}),\dots,(p_{n},w_{n})$ with weights
$w_{i}\in\mathbb{N}$ and profits $p_{i}$ being multiples of $\varepsilon$ in
the interval $[1,2)$, compute a profit function that
$(1-\varepsilon)$-approximates $f_{I}$ up to $2/\varepsilon$.

######  Lemma 3.1.

If for some $c\geq 2$, 2 can be solved in $\tilde{O}(n+1/\varepsilon^{c})$
time, then $(1-\varepsilon)$-approximating _Knapsack_ can also be solved in
$\tilde{O}(n+1/\varepsilon^{c})$ time.

The proof of Lemma 3.1 can be seen in the appendix.

The following useful lemma allows us to merge multiple profit functions, which
was proven by Chan using divide-and-conquer and improved algorithms for
$(\min,+)$-convolution [BCD+14, Wil14, CW16].

######  Lemma 3.2 ([Cha18, Lemma 2(i)]).

Let $f_{1},\dots,f_{m}$ be monotone step functions with total complexity $N$
and ranges contained in $\\{-\infty,0\\}\cup[A,B]$. Then we can compute a
monotone step function that has complexity
$\tilde{O}(\frac{1}{\varepsilon}\log B/A)$ and
$(1-O(\varepsilon))$-approximates $f_{1}\oplus\dots\oplus f_{m}$, in
$O(N)+\tilde{O}((\frac{1}{\varepsilon})^{2}m/2^{\Omega(\sqrt{\log(1/\varepsilon)})}\log
B/A)$ time.

The following reduction was used in [DJM23].

######  Lemma 3.3.

Given a list $I$ of $n$ items with $p_{i}$ being multiples of $\varepsilon$ in
interval $[1,2)$, and integer $1\leq m\leq n$ with $m=O(1/\varepsilon)$, if
for some $c\geq 2$ one can compute a profit function that
$(m\varepsilon)$-additively approximates $f_{I}$ up to $2m$ in
$\tilde{O}(n+1/\varepsilon^{c})$ time . Then one can
$(1-\varepsilon)$-approximate _Knapsack_ in $\tilde{O}(n+1/\varepsilon^{c})$
time.

###### Proof.

From Lemma 3.1, it suffices to approximate 2. We divide
$[1,2\varepsilon^{-1})$ into $O(\log(1/\varepsilon))$ many intervals $[m,2m)$
where $m$’s are powers of 2, and for each $m$, compute profit functions
$f_{m}$ achieving $m\varepsilon$-additive approximation up to $2m$. For each
$x\geq 0$, let $m_{x}$ be such that $m_{x}\leq f_{I}(x)<2m_{x}$. Then
$f_{m_{x}}(x)\in[f_{I}(x)-m_{x}\varepsilon,f_{I}(x)]$. Since $f_{I}(x)\geq
m_{x}$, $f_{m_{x}}(x)\in[f_{I}(x)(1-\varepsilon),f_{I}(x)]$. Thus taking the
pointwise maxima of all $f_{m}$’s yields a $(1-\varepsilon)$ approximation of
$f_{I}$. Note that by using the rounding scheme mentioned before we can make
the complexity of each profit function $\tilde{O}(1/\varepsilon)$. Therefore
taking the pointwise maxima of all $f_{m}$’s takes
$O(\log(1/\varepsilon))\times\tilde{O}(1/\varepsilon)=o(n+1/\varepsilon^{c})$
time. ∎

As an ingredient, we use a corollary of Lemma 7 of [Cha18]. The corollary
states that profit functions can be approximately more efficiently when there
are few distinct profit values or when there is a good upper bound on profit
values. We first present the lemma in its original form. A step function $f$
is $p$-uniform if the function values are of the form $-\infty,0,p,2p,\cdots
lp$ for some non-negative integer $l$. A $p$-uniform function is pseudo-
concave if the sequence of differences of consecutive $x$-breakpoints is non-
decreasing.

######  Lemma 3.4 (Lemma 7 of [Cha18]).

Let $f_{1},...,f_{m}$ be monotone step functions with ranges contained in
$\\{-\infty,0\\}\cup[1,B]$. If every $f_{i}$ is $p_{i}$-uniform and pseudo-
concave for some $p_{i}\in[1,2],$ then we can compute a monotone step function
that $(1-\varepsilon)$-approximates $\min(f_{1}\oplus\cdots\oplus f_{m},B)$
and complexity $\tilde{O}(\frac{1}{\varepsilon})$ in
$\tilde{O}(\sqrt{B}m/\varepsilon)$ deterministic333The original lemma used the
word ”expected” since it was initially randomized due to a randomized
construction for a number theoretical lemma, but Chan later derandomized it in
the same paper. A simpler deterministic construction can be seen in Lemma 3.11
of [DJM23]. time, assuming $B=\tilde{O}(1/\varepsilon).$

######  Corollary 3.5.

Given a list $I$ of items $(p_{1},w_{1}),\dots,(p_{n},w_{n})$ with weights
$w_{i}\in\mathbb{N}$ and profits $p_{i}$ being multiples of $\varepsilon$ in
the interval $[1,2)$, if there are only $\Delta$ distinct profit values
$p_{i}$, then for any $B=\tilde{O}(1/\varepsilon)$, one can
$(1-\varepsilon)$-approximate $\min(f_{I},B)$ (i.e. $f_{I}$ up to $B$) in
$\tilde{O}(n+\Delta\sqrt{B}\varepsilon^{-1})$ time.

###### Proof.

Note that $I=I_{1}\cup I_{2}\cup\cdots\cup I_{\Delta}$ where each $I_{j}$
contains items of the same profit value. It suffices to compute
$\min(f_{I_{1}}\oplus\cdots\oplus f_{I_{\Delta}},B)$. Fix $j\in[1,\Delta]$. If
we let ${w^{\prime}}_{k}$ be the $k$-th smallest weight in $I_{j}$, then:

  * •

For every $0\leq k\leq\left\lvert I_{j}\right\rvert-1$, for
$x\in\left[\sum_{1\leq k^{\prime}\leq
k}{{w^{\prime}}_{k^{\prime}}},\sum_{1\leq k^{\prime}\leq
k+1}{{w^{\prime}}_{k^{\prime}}}\right)$ we have $f_{I_{j}}(x)=kp_{j}$.

  * •

$f_{I_{j}}\left(\sum_{1\leq k^{\prime}\leq\left\lvert
I_{j}\right\rvert}{{w^{\prime}}_{k^{\prime}}}\right)=\left\lvert
I_{j}\right\rvert p_{j}$.

It is easy to see that $f_{I_{j}}$ is $p_{j}$-uniform and pseudo-concave with
$p_{j}\in[1,2]$. Furthermore, for each $j$ it suffices to compute
$\min(f_{I_{j}},B)$, whose range is contained in $\\{-\infty,0\\}\cup[1,B]$.
From Lemma 3.4 we can compute $\min(f_{I_{1}}\oplus\cdots\oplus
f_{I_{\Delta}},B)$ in $\tilde{O}(\sqrt{B}m/\varepsilon)$ time. Constructing
$\min(f_{I_{j}},B)$ all $j$’s takes $\tilde{O}(n)$ time. The total time
complexity is $\tilde{O}(n+\Delta\sqrt{B}/\varepsilon)$. ∎

###  3.2 Greedy Exchange Lemma

We now introduce the Greedy Exchange Lemma previously employed in [DJM23]. We
will follow the framework in [DJM23]. Given items
$(p_{1},w_{1}),\dots,(p_{n},w_{n})$, where $p_{i}\in[1,2)$ are multiples of
$\varepsilon$, we sort them by non-increasing order of unit profit:
$p_{1}/w_{1}\geq p_{2}/w_{2}\geq\dots\geq p_{n}/w_{n}$.

Then, we consider prefixes of this sequence of items, and define the following
measure of diversity:

######  Definition 3.6 ($D(i)$).

For $1\leq i\leq n$, let $D(i)=\min_{J}C([i]\setminus J)$, where the
minimization is over all subsets $J\subseteq[i]$ with $|J|\leq 2m$, and
$C([i]\setminus J)$ denote the number of distinct values in
$\\{p_{j}:j\in[i]\setminus J\\}$.

We have the following immediate observations about $D(i)$:

######  Observation 3.7.

  1. 1.

For all $2\leq i\leq n$, $0\leq D(i)-D(i-1)\leq 1$.

  2. 2.

$D(i)$ (and the minimizer $J$) can be computed in $\tilde{O}(i)$ time by the
following greedy algorithm: start with all values $p_{1},p_{2},\cdots,p_{i}$.
Repeat the following up to $2m$ times: remove the value $p_{j}$ with the
minimum multiplicity, and add $j$ into $J$.

######  Definition 3.8 ($i^{\Delta}$).

For some parameter $\Delta$, define ${i^{\Delta}}\in\\{1,2,\dots,n\\}$ be the
maximum such that $D({i^{\Delta}})\leq\Delta$, which can be found using 3.7
with a binary search in $\tilde{O}(n)$ time.

In [DJM23], the following lemma was proven. Recall that Corollary 3.5
guarantees a faster run time when we have a bound on profit values. The goal
of the lemma is to impose a bound on the total profit items in
$[n]\setminus[{i^{\Delta}}]$ can contribute. On a high level, it argues that,
given any subset $S$ of items, we can swap out some items in
$S\cap([n]\setminus[{i^{\Delta}}])$ with items in $[{i^{\Delta}}]$, resulting
in a new subset $\tilde{S}$ that is not too much worse than $S$, but the
contribution from $[n]\setminus[{i^{\Delta}}]$ to $\tilde{S}$ is small.

######  Lemma 3.9.

[Greedy Exchange Lemma, Lemma 3.9 of [DJM23]] Let $S\subseteq[n]$ be any item
set with total profit $\sum_{s\in S}p_{s}\leq 2m$. Let
$\Delta=\omega(\varepsilon^{-1/2}\log^{1/2}{(1/\varepsilon)})$ be some
parameter. Let $B:=c\varepsilon^{-1}/\Delta$ for some universal constant
$c\geq 1$.

Then, there exists an item set $\tilde{S}\subseteq[n]$, such that the total
profit $\tilde{p}$ contributed by items $[n]\setminus[{i^{\Delta}}]$ in
$\tilde{S}$ satisfies

$\tilde{p}:=\sum_{s\in\tilde{S}\cap([n]\setminus[{i^{\Delta}}])}p_{s}\leq B,$
(1)

and

$\sum_{s\in\tilde{S}}p_{s}\geq(1-\varepsilon)\sum_{s\in S}p_{s},$ (2)

and

$\sum_{s\in\tilde{S}}w_{s}\leq\sum_{s\in S}w_{s}.$ (3)

The proof is included in the appendix for completeness.

In [DJM23], we have $\Delta:=\lfloor\varepsilon^{-5/8}\rfloor$, which
satisfies the condition in Lemma 3.9.

The reduction in [DJM23] uses the following lemma for
$(1-\varepsilon)$-approximating knapsack up to a small $B$:

######  Lemma 3.10 (Follows from Lemma 17 of [Jin19]).

Given a list $I$ of items $(p_{1},w_{1}),\dots,(p_{n},w_{n})$ with weights
$w_{i}\in\mathbb{N}$ and profits $p_{i}$ being multiples of $\varepsilon$ in
the interval $[1,2)$, one can $(1-\varepsilon)$-approximate the profit
function $f_{I}$ up to $B$ in
$\tilde{O}(n+\varepsilon^{-2}B^{1/3}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$
time.

Finally, a weaker version of Lemma 2.3 was proven in [DJM23] using random
partitioning.

######  Lemma 3.11.

[Lemma 3.6 of [DJM23]]

1 can be solved in ramdomized
$\tilde{O}(n^{{4}/{5}}\varepsilon^{-{7}/{5}}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$
time.

In [DJM23], a randomized running time of
$\tilde{O}(n+\varepsilon^{-11/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$ was
achieved for 2 by combining the following lemma with Lemma 3.3. To finish our
introduction for techniques in [DJM23], we will also include its proof.

######  Lemma 3.12 (Lemma 3.5 of [DJM23]).

Given a list $I$ of $n$ items with $p_{i}$ being multiples of $\varepsilon$ in
interval $[1,2)$, and integer $1\leq m\leq n$ with $m=O(1/\varepsilon)$, one
can compute a profit function that $(m\varepsilon)$-additively approximates
$f_{I}$ up to $2m$ in
$O(n+\varepsilon^{-11/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$ time .

###### Proof of Lemma 3.12.

Recall that we have $\Delta:=\lfloor\varepsilon^{-5/8}\rfloor$, and that
$i^{\Delta}\in\\{1,2,\dots,n\\}$ is the maximum such that
$D(i^{\Delta})\leq\Delta$, which can be found using 3.7 with a binary search
in $\tilde{O}(n)$ time. Let $J\subset[i^{\Delta}]$ with $|J|\leq 2m$ be the
minimizer for $D(i^{\Delta})$.

Now, we approximately compute the profit functions
$f_{J},f_{[i^{\Delta}]\setminus J},f_{[n]\setminus[i^{\Delta}]}$ for three
item sets $J,[i^{\Delta}]\setminus J,[n]\setminus[i^{\Delta}]$ using different
algorithms, described as follows:

  1. 1.

Use Lemma 3.11 to compute $f_{1}$ that $(2m\varepsilon)$-additively
approximates $f_{J}$ in
randomized$O(m^{\frac{4}{5}}\varepsilon^{-\frac{7}{5}}/2^{\Omega(\sqrt{\log(1/\varepsilon)}})\leq
O(\varepsilon^{-\frac{11}{5}}/2^{\Omega(\sqrt{\log(1/\varepsilon)}})$ time.

  2. 2.

By the definition of $i^{\Delta}$, items in $[i^{\Delta}]\setminus J$ have no
more than $\Delta$ distinct profit values. Hence we can use Corollary 3.5 to
compute $f_{2}$ that $(1-\varepsilon)$-approximates $f_{[i^{\Delta}]\setminus
J}$ up to $2m$, in
$\tilde{O}(n+\Delta\sqrt{2m}\varepsilon^{-1})=\tilde{O}(\varepsilon^{-17/8})$
time.

  3. 3.

Use Lemma 3.10 to compute $f_{3}$ that $(1-\varepsilon)$-approximates the
$f_{[n]\setminus[i^{\Delta}]}$ up to
$B=c\varepsilon^{-1}/\Delta=\Theta(\varepsilon^{-1}/\Delta)$ where $c$ is the
universal constant in Lemma 3.9, in
$\tilde{O}(B^{1/3}\varepsilon^{-2})\leq\tilde{O}(\varepsilon^{-17/8})$ time.

Finally, merge the three parts $f_{1},f_{2},f_{3}$ using Lemma 3.2 in
$\tilde{O}(\varepsilon^{-2})$ time, and return the result.

In the third part, the correctness of only computing up to $B$ is justified by
Lemma 3.9, which shows that if we only consider approximating sets with total
profit up to $2m$, then we can assume the items in $[n]\setminus[i^{\Delta}]$
only contributes profit at most $B$ (1), at the cost of only incurring an
$(1-\varepsilon)$ approximation factor (2).

To analyze the error, notice that in the first part we incur an additive error
of $2m\varepsilon$. In the second and third part and the final merging step we
incur $(1-O(\varepsilon))$ multiplicative error, which turns into
$O(m\varepsilon)$ additive error since we only care about approximating up to
$2m$. Hence the overall additive error is $O(m\varepsilon)$, which can be made
$m\varepsilon$ by lowering the value of $\varepsilon$. ∎

Our new algorithm will use a new reduction that uses the Greedy Exchange Lemma
recursively. Intuitively, observe that the computation of $f_{3}$ is a reduced
version of the original problem with a stricter upper bound, so instead of
computing it directly, we can apply the procedure recursively.

###  3.3 Past Algorithms for Knapsack

####  3.3.1 Chan’s Framework

We can easily see that the extra running time incurred by the reduction in
Lemma 3.12 on top of solving 1 is $\tilde{O}(\varepsilon^{-17/8})$, which is
dominated by the factor $\varepsilon^{-11/5}$ in Lemma 3.11. Therefore, the
most important reason that we are able to obtain a speedup in our new
algorithm is due to the improvement from Lemma 3.11 to Lemma 2.3, namely a
better running time for 1: See 1

Improving the running time for 1 and for Knapsack have been very challenging
tasks in the recent years. This is mainly due to the inability to go around
the trade-off between two different approaches: the sequential approach that
is efficient at the cost of precision, and the divide-and-conquer approach
that is precise at the cost of efficiency. We now briefly introduce them and
will limit our discussion on 1 for now for simplicity.

In the sequential approach, we go through items in $I$ one by one and update
the profit function. The classical dynamic programming solution to _knapsack_
can be seen as an analog in the deterministic case. Suppose the total profit
value of items seen so far is $P_{i}:=\sum_{j\leq i}{p_{j}}$. The profit
function for the first $i$ items has a complexity of $O(P_{i})$ and updating
the profit function with the addition of a single item can easily be done in
$O(P_{i})$ time. In the approximate case, we perform rounding on the profit
function after each addition. Since errors from sequential rounding add up, to
guarantee a final additive error of $n\varepsilon$, one has to round to
multiples of $\varepsilon$. Since $P_{i}=O(n)$, this unfortunately makes the
complexities of profit functions $O(n\varepsilon^{-1})$ and the total running
time becomes $O(n^{2}\varepsilon^{-1})=O(\varepsilon^{-3})$.

An alternative method is to use divide and conquer. Without loss of generality
assume that $\left\lvert I\right\rvert$ is a power of $2$, We divide $I$ into
two equal parts $I=X\cup Y$. We approximate the profit functions $f_{X}$ and
$f_{Y}$ recursively and approximate $f_{I}=f_{X}\oplus f_{Y}$. Every time we
are in a sub-problem with total profit value $P$, we round to multiples of
$P\varepsilon$, and we can show that the total additive error is
$O(n\varepsilon\log n)=\tilde{O}(n\varepsilon)$. Thus we can keep the
complexities of profit functions $O(\varepsilon^{-1})$. However, we have to
merge two profit functions of complexity $O(\varepsilon^{-1})$ for each of the
$O(n)$ sub-problems in the entire recursion tree, which is a
$(\max,+)$-convolution that generally takes quadratic time. Therefore we still
only have a running time of
$\tilde{O}(n\varepsilon^{-2})=\tilde{O}(\varepsilon^{-3})$.

As shown by Chan [Cha18], assuming that $n=O(\varepsilon^{-1})$, one can
achieve a running time of $\tilde{O}(\varepsilon^{-2.5})$ by combining these
two ideas: divide $I$ into $\varepsilon^{-0.5}$ chunks of size
$O(\varepsilon^{-0.5})$, solve for each chunk sequentially and use divide-and-
conquer to merge the answers for chunks. Chan’s original version was a
slightly more complicated algorithm directly for Knapsack with a running time
of $\tilde{O}(n+\varepsilon^{-2.5})$ as the reduction of the form of Lemma
3.12 did not exist back then.

Obtaining further improvements for either 1 or Knapsack has been an arduous
endeavor, and such improvements have all been based on Chan’s framework. In
the same work, Chan observed that in the sequential method, instead of
repeated rounding at each item, if all $p_{i}$’s are close to multiples of
some large number $p^{\prime}$, we can simply round everything to multiples of
$p^{\prime}$ at the beginning. Chan employed a number theoretical lemma
stating that it is possible to group items into groups where items in each
group is close to multiples of some large number, and achieved a running time
of $\tilde{O}(n+\varepsilon^{-12/5})$ for Knapsack and
$\tilde{O}(\varepsilon^{-7/3})$ for 1. Jin [Jin19] extended the technique to
multiple layers and combined it with greedy, resulting in a running time of
$\tilde{O}(n+\varepsilon^{-9/4})$ for Knapsack and
$\tilde{O}(\varepsilon^{-9/4})$ for 1. The reduction in Lemma 3.12 was
proposed in the algorithm by Deng, Jin and Mao [DJM23], which used Jin’s
previous results as ingredients. They also used a randomized partitioning
technique for limiting the scope of $(\max,+)$-convolution to achieve a
running time of $\tilde{O}(\varepsilon^{-11/5})$ for 1 and a running time of
$\tilde{O}(n+\varepsilon^{-11/5})$ for Knapsack. As we can see, not only have
improvements been more and more marginal, but the algorithms that achieve them
have also increased in complexity.

####  3.3.2 Sparsification for Subset Sum and Its Potential on Knapsack

Researchers have struggled much less on the related problem of approximating
subset-sum. The first algorithm with a running time of
$\tilde{O}(n/\varepsilon)$ was known in the 70s [GL79], and the first
algorithm that achieves a running time of $\tilde{O}(n+\varepsilon^{-2})$ was
known in 1997 [KPS97]. Recently, Bringmann and Nakos [BN21] improved the
running time to
$\tilde{O}(n+\varepsilon^{-2}/2^{\Omega(\sqrt{\log(1/\varepsilon)})})$ and
showed a matching lower bound based on the $(\min,+)$-convolution hypothesis.
Bringmann and Nakos showed the sparsification technique for reducing the size
of sets of subset-sums we need to store without losing any precision, which,
if employed to knapsack, could give us a best-of-both-worlds solution that
achieves efficiency and precision at the same time.

We will give a brief introduction of this technique. For simplicity, we only
discuss additive approximation. A $\Delta$-additive approximation of a set $S$
is a set $S^{\prime}$ such that $\forall x\in S,\exists x^{\prime}\in
S^{\prime},x-\Delta\leq x^{\prime}\leq x$ and $\forall x^{\prime}\in
S^{\prime},\exists x\in S,x-\Delta\leq x^{\prime}\leq x$. Let $S$ be a set of
numbers. To “sparsify” $S$, we recursively do the following: if there exists
$u,v,w\subset S$ such that $u<v<w\leq u+\Delta$, remove $v$ from $S$. In the
resulting set, for every three consecutive numbers $u<v<w$, we have
$w-u>\Delta$. Thus if $S\subset[0,B]$, then the sparsification $S^{\prime}$
has a size of $O(B/\Delta)$. Suppose we have two sets $S_{X}$ and $S_{Y}$
representing possible subset sums of two disjoint sets $X$ and $Y$, and we
want to approximate $\\{x+y\mid x\in S_{X},y\in S_{Y}\\}$ which is the set of
possible subset sums of $X\cup Y$. Suppose the sparsifications of $S_{X}$ and
$S_{y}$ are $\hat{S}_{X}$ and $\hat{S}_{Y}$. It is proven in [BN21] that the
set $\\{x+y\mid x\in\hat{S}_{X},y\in\hat{S}_{y}\\}$ is a
$\Delta$-approximation (rather than $2\Delta$-approximation) of the set
$\\{x+y\mid x\in S_{X},y\in S_{Y}\\}$. In other words, individual rounding
errors do not accumulate.

Unfortunately, the simplest analog of sparsification for profit function fails
to prevent accumulation of rounding errors. Suppose that to “sparsify” a
profit function $f$, we recursively do the following: if there exist three
consecutive $x$-breakpoints $u,v,w$ such that $f(u)<f(v)<f(w)\leq
f(u)+\Delta$, we remove the x-breakpoint at $v$ so that in the sparsification
$f^{\prime}$, $f^{\prime}(i)=f(u)$ for $i\in[u,w)$. In the following example,
the sparsification $f^{\prime}$ for profit functions $f$ is such that
$f^{\prime}\oplus f^{\prime}$ is only a $(2\Delta-2)$-additive approximation
for $f\oplus f$. Suppose $f(x)=-\infty$ for $x<0$, $f(x)=0$ for $0\leq x<1$,
$f(x)=\Delta-1$ for $1\leq x<2$, and $f(x)=\Delta$ for $x\geq 2$. In the
sparsification $f^{\prime}$, the x-breakpoint for at $x=1$ is removed and we
have $f^{\prime}(x)=-\infty$ for $x<0$, $f^{\prime}(x)=0$ for $0\leq x<2$, and
$f(x)=\Delta$ for $x\geq 2$. Then we have $(f\oplus f)(2)=2\Delta-2$ but
$(f^{\prime}\oplus f^{\prime})(2)=0$.

The core idea in this paper is a sophisticated way of sparsifying profit
functions without accumulation of rounding errors. The sparsified results can
be described by a small amount of convex hulls on a 2D plane. We will use
techniques in computational geometry to merge these convex hulls, resulting in
the final quadratic running time.

##  4 Main Algorithm

###  4.1 Reduction to the Sparse Case via Recursive Greedy Exchange

In this subsection, we will prove the following:

######  Lemma 4.1.

Given a list $I$ of $n$ items with $p_{i}$ being multiples of $\varepsilon$ in
interval $[1,2)$, and integer $1\leq m\leq n$ with $m=O(1/\varepsilon)$, one
can compute a profit function with complexity $\tilde{O}(\varepsilon^{-1})$
that $(m\varepsilon)$-additively approximates $f_{I}$ up to $2m$ in
$\tilde{O}(n+\varepsilon^{-2})$ time.

Lemma 4.1 implies Theorem 1.1 due to Lemma 3.3. Our core ingredient is Lemma
2.3 which will be proved in Section 4.2: See 1 See 2.3

Also recall Corollary 3.5: See 3.5

To prove Lemma 4.1, we will use the proof in Lemma 3.12 in a recursive manner.
We solve the following problem for a variety of parameters $B$. Assume that
$C>0$ is a universal large constant.

######  Problem 3.

Given a list $I$ of $n$ items with $p_{i}$ being multiples of $\varepsilon$ in
interval $[1,2)$, integer $1\leq m\leq n$ with $m=O(1/\varepsilon)$, integer
$k>0$, as well as a number $1\leq B\leq 2m$, compute a profit function that
$(Ckm\varepsilon)$-additively approximates $f_{I}$ up to $B$.

######  Lemma 4.2.

Let $T(n,m,B,k)$ be the running time for 3 with parameters $n,m,k$ and $B$.
Then there exists $B^{\prime}=o(B^{1/2})$ and $n^{\prime}\leq n$ such that:

$T(n,m,B)=\tilde{O}(n+\varepsilon^{-2})+T(n^{\prime},m,B^{\prime}).$

###### Proof.

To solve the problem for $(n,m,k,B)$, we set

$\Delta:=\Theta((\varepsilon^{-1}/B^{1/2})\log{(1/\varepsilon)})=\omega(\varepsilon^{-1/2}\log^{1/2}{(1/\varepsilon)}).$

Recall Definition 3.6, 3.7 and Definition 3.8.
${i^{\Delta}}\in\\{1,2,\dots,n\\}$ is the maximum such that
$D({i^{\Delta}})\leq\Delta$, which can be found using with a binary search in
$\tilde{O}(n)$ time. Let $J\subset[{i^{\Delta}}]$ with $|J|\leq 2m$ be the
minimizer for $D({i^{\Delta}})$.

As in the proof of Lemma 3.12, we approximately compute the profit functions
$f_{J},f_{[{i^{\Delta}}]\setminus J},f_{[n]\setminus[{i^{\Delta}}]}$ for three
item sets $J,[{i^{\Delta}}]\setminus J,[n]\setminus[{i^{\Delta}}]$ using
different algorithms, described as follows:

  1. 1.

Use Lemma 2.3 to compute $f_{1}$ that $(2m\varepsilon)$-additively
approximates $f_{J}$, in $\tilde{O}(\varepsilon^{-2})$ time.

  2. 2.

By definition of ${i^{\Delta}}$, items in $[{i^{\Delta}}]\setminus J$ have no
more than $\Delta$ distinct profit values. Since we only need to approximate
up to $B$, we can use Corollary 3.5 to compute $f_{2}$ that
$(1-\varepsilon)$-approximates $\min(f_{[{i^{\Delta}}]\setminus J},B)$ in
$\tilde{O}(n+\Delta\sqrt{B}\varepsilon^{-1})=\tilde{O}(n+\varepsilon^{-2})$
time.

  3. 3.

We $C(k-1)m\varepsilon$-additively approximate $\min(f_{3},B^{\prime})$ for
$B^{\prime}=c\varepsilon^{-1}/\Delta=o(B^{1/2})$ where $c$ is the universal
constant in Lemma 3.9. This is equivalent to 3 with parameters
$(n^{\prime},m,k-1,B^{\prime})$ where $n^{\prime}=n-i^{\Delta}$, and can be
done in $T(n^{\prime},m,k-1,B^{\prime})$ time.

Finally, merge the three parts $f_{1},f_{2},f_{3}$ using Lemma 3.2 in
$\tilde{O}(n+\varepsilon^{-2})$ time, and return the result. The total running
time is $\tilde{O}(n+\varepsilon^{-2})+T(n^{\prime},m,B^{\prime})$.

In the third part, the correctness of only computing up to $B^{\prime}$ is
justified by Lemma 3.9, which shows that if we only consider approximating
sets with total profit up to $2m\geq B$, then we can assume the items in
$[n]\setminus[{i^{\Delta}}]$ only contributes profit at most $B^{\prime}$
(Inequality 1), at the cost of only incurring an
$(1-\varepsilon)$-approximation factor (Inequality 2).

To analyze the error, notice that in the first part, we incur an additive
error of $2m\varepsilon$. In the second part and the final merging step we
incur $(1-O(\varepsilon))$ multiplicative error, which turns into
$O(m\varepsilon)$ additive error since we only care about approximating up to
$B\leq 2m$. Hence the additive error for these parts is $O(m\varepsilon)$. By
letting the constant $C$ be large we can assume that the overall additive
error is at most $Cm\varepsilon$. Finally, the third part incurs an additive
error of $C(k-1)m\varepsilon$. Hence the overall additive error is at most
$C(k-1)m\varepsilon+Cm\varepsilon=Ckm\varepsilon$. ∎

We are now ready to prove Lemma 4.1

###### Proof of Lemma 4.1.

Note that 3 is trivial when $B<2$. Note that for any value no more than $2m$,
by recursively taking its square root at most $O(\log\log m)$ times, we get a
value less than $2$. Note that in Lemma 4.2 we always have
$B^{\prime}<B^{1/2}$. Thus the running time for $T(n,m,k,2m)$ is a summation
of at most $O(\log\log m)$ repetitions of the term
$\tilde{O}(n+\varepsilon^{-2})$, as long as $k$ is larger than the number of
repetitions. Hence, for $k=\omega(\log\log m)$ we have:

$T(n,m,k,2m)\leq O(\log\log
m)\times\tilde{O}(n+\varepsilon^{-2})=\tilde{O}(n+\varepsilon^{-2}).$

Namely, we can solve 3 in $\tilde{O}(n+\varepsilon^{-2})$ time for
$(n,m,k,2m)$ as long as $k=\omega(\log\log m)$. Thus for
$k=O(\log(1/\varepsilon))$ , we can get an
$O(m\varepsilon\log(1/\varepsilon))$-additive approximation for the problem in
Lemma 4.1 $\tilde{O}(n+\varepsilon^{-2})$ time, which can be made into an
$m\varepsilon$-additive approximation by lowering the value of $\varepsilon$
by a polylogarithmic factor. ∎

###  4.2 Approximation for the Sparse Case via Geometry

####  4.2.1 Definitions

In this section, we prove our core lemma: See 2.3

First we recall the relevant definitions. The contour of a profit function
with domain $x\in[x_{1},x_{k}]$ with a complexity of $k$ can be described by a
set444A set must contain distinct elements. $P(f)$ of $(2k-1)$ 2-D points

$\\{(x_{1},y_{1}),(x_{2},y_{1}),(x_{2},y_{2}),(x_{3},y_{2}),\cdots,(x_{k},y_{k-1}),(x_{k},y_{k})\\}$

with $x_{1}<x_{2}<\cdots<x_{k}$ and $y_{1}<y_{2}<\cdots<y_{k}$, where
$f(x)=y_{i}$ for $x_{i}\leq x<x_{i+1}(1\leq i\leq n)$.

A set of points $P=\\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{k},y_{k})\\}$
satisfying $x_{i}\leq x_{i+1}$ and $y_{i}\leq y_{i+1}$ for $1\leq i\leq k-1$
and $x_{i+2}>x_{i}$ for $1\leq i\leq k-2$ is called a _monotone point set_.
The profit function $f(P)$ with domain $[x_{1},x_{k}]$ is defined as
$(f(P))(x)=y_{i}$ for $x_{i}\leq x<x_{i+1}$ for $1\leq i<k$ and
$(f(P))(x_{k})=y_{k}$.

For a set $S$ of points in the 2D plane, let
${\min}_{x}{S},\max_{x}{S},{\min}_{y}{S}$ and ${\max}_{y}{S}$ be the minimum
x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the
maximum y-coordinate of points in $S$.

For a point $p$ on the 2D plane, we let $p_{x}$ and $p_{y}$ be its
x-coordinate and y-coordindate respectively. For two distinct points $p$ and
$q$, we say $p<q$ if either $p_{x}<q_{x}$ or $p_{x}=q_{x}$ and $p_{y}<q_{y}$.
Given two points $p$ and $q$, let $r:=p+q$ be the point with
$r_{x}=p_{x}+q_{x}$ and $r_{y}=p_{y}+q_{y}$, and let $r:=p-q$ be the point
with $r_{x}=p_{x}-q_{x}$ and $r_{y}=p_{y}-q_{Y}$. Given a point $p$ and a
point set $S$, let $p+S:=S+p:=\\{p+s\mid s\in S\\}$. Given two sets of points
$A$ and $B$, their _Minkowski sum_ is defined as $A+B=\\{a+b\mid a\in A,b\in
B\\}.$

For a monotone point set $P$, the set of segments $E(P)$ are the line segments
between adjacent points in $P$: $E(P):=\\{(p_{i},p_{i+1})\mid 1\leq
i<\left\lvert P\right\rvert\\}$. The region $R(P)$ is defined to be the set of
points $(x,y)(x_{1}\leq x\leq x_{k},y\geq 0)$ on or below the segments $E(P)$.
For $x_{1}\leq x\leq x_{k}$, let $g[P](x)$ be equal to the maximum
y-coordinate of a point on the upper boundary of $R(P)$ with x-coordinate
equal to $x$. For any $1\leq i\leq\left\lvert P\right\rvert$, if
$i\in\\{1,\left\lvert P\right\rvert\\}$ or the point $p_{i}$ is above the line
segment connecting $p_{i-1}$ and $p_{i+1}$, we call the point $p_{i}$ an
_apex_ of $P$. If $i\notin\\{1,\left\lvert P\right\rvert\\}$ and the point
$p_{i}$ is below the line segment connecting $p_{i-1}$ and $p_{i+1}$, we call
the point $p_{i}$ a _base_ of $P$. If $i\notin\\{1,\left\lvert
P\right\rvert\\}$ and the point $p_{i}$ is on the line segment connecting
$p_{i-1}$ and $p_{i+1}$, we call the point $p_{i}$ _degenerate_.

$R(P)$$g[P]$$f(P)$$\delta$ABCDEFG$x$$y$ Figure 1: Monotone Point Set
$P=\\{A,B,C,D,E,F,G\\}$

For example, in Fig. 1, the set $P=\\{A,B,C,D,E,F,G\\}$ is a monotone point
set. The region $R(P)$ is the shaded region below the thick red curve, which
is the plot of $g[P]$. The plot of $f(P)$ is the thin blue line. For instance,
$C$ is an apex since it is above the line connecting $B$ and $D$, and $B$ is a
base since it is below the line connecting $A$ and $C$. We will see an example
of a degenerate point later.

Given two monotone point sets $P_{a}$ and $P_{b}$, let $P_{a}\oplus P_{b}$ be
the minimum set $V$ of points such that $R(V)=R(P_{a})+R(P_{b})$. It is easy
to verify that $V$ is a monotone point set without degenerate points.

It is well-known [dBvKOS00] that the Minkowski sum of two polygons $P$ and $Q$
with $\left\lvert P\right\rvert$ and $\left\lvert Q\right\rvert$ vertices is
the union of $\left\lvert P\right\rvert$ translations of $Q$ and $\left\lvert
Q\right\rvert$ translations of $P$ consisting of:

  * •

$p+Q$ for each $p\in P$, and

  * •

$P+q$ for each $q\in Q$.

It is also easy to verify that $g[P_{a}\oplus P_{b}]=g[P_{a}]\oplus g[P_{b}]$.

####  4.2.2 Roadmap

We will show an analog of the “sparsification” technique in [BN21] in 2D. We
can approximate a profit function $f$ with a monotone point set. To start, we
can see that $P(f)$ can approximate $f$ exactly. We now show a way to reduce
the monotone point set associated with a profit function so that we can still
approximate the profit function with the reduced monotone point set, and the
rounding errors do not accumulate when combining two profit functions and
their monotone point set approximations.

######  Definition 4.3 ($F$-generatability).

For a parameter $\delta:=\varepsilon n$, and a set of $m$ profit functions
$F=\\{f_{1},f_{2},\cdots,f_{m}\\}$, we define the notion of $F$-generatability
on a pair consisting of a profit function and a monotone point set based on
the three operations below:

  1. 1.

For each $f\in F$, $(f,P(f))$ is $F$-generatable.

  2. 2.

If $(f_{a},P_{a})$ and $(f_{b},P_{b})$ are both $F$-generatable, $(f_{a}\oplus
f_{b},P_{a}\oplus P_{b})$ is also $F$-generatable;

  3. 3.

Suppose $(f,P)$ is $F$-generatable. Suppose we perform a _reduction_ on $P$:
find two apexes $x,y\in P$ on $P$ with $0<y_{y}-x_{y}\leq\delta$ such that all
points strictly between $x$ and $y$ are below the line segment connecting $x$
and $y$, let $\accentset{\rule{2.79996pt}{0.6pt}}{P}$ be $P$ with all points
between $x$ and $y$ removed. Let $P^{\prime}$ be the minimum subset of
$\accentset{\rule{2.79996pt}{0.6pt}}{P}$ with
$R(P^{\prime})=R(\accentset{\rule{2.79996pt}{0.6pt}}{P})$ (i.e.
$\accentset{\rule{2.79996pt}{0.6pt}}{P}$ with degenerate points removed). Then
the new pair $(f,P^{\prime})$ is $F$-generatable.

To explain Operation 3, suppose $P=\\{A,B,C,D,E,F,G\\}$ as shown in Fig. 1,
and suppose $\delta$ is equal to the difference in y-coordinates between $C$
and $F$. For $(x,y)=(C,F)$, since both $D$ and $E$ are below the line segment
connecting $C$ and $F$, we can remove them and get
$\accentset{\rule{2.79996pt}{0.6pt}}{P}=\\{A,B,C,F,G\\}$. Note that since $F$
is on the segment connecting $C$ and $G$, it is a degenerate point of
$\accentset{\rule{2.79996pt}{0.6pt}}{P}$ and is removed from
$\accentset{\rule{2.79996pt}{0.6pt}}{P}$ to obtain $P^{\prime}=\\{A,B,C,G\\}$.
We can not perform Operation 3 for $(x,y)=(A,F)$ despite all points between
them being below the segment since $F_{y}-A_{y}>\delta$.

It is easy to see that if $(f,P)$ is $F$-generatable for some $F$, then $P$
contains no degnerate points.

Solving 1 is equivalent to combining $n$ profit functions
$\accentset{\rule{2.79996pt}{0.6pt}}{F}=\\{\accentset{\rule{2.79996pt}{0.6pt}}{f}[1],\accentset{\rule{2.79996pt}{0.6pt}}{f}[2],\cdots,\accentset{\rule{2.79996pt}{0.6pt}}{f}[n]\\}$
where $\accentset{\rule{2.79996pt}{0.6pt}}{f}[i]$ has a domain of $[0,w_{i}]$
and $\accentset{\rule{2.79996pt}{0.6pt}}{f}[i](x):=0$ for $0\leq x<w_{i}$ and
$\accentset{\rule{2.79996pt}{0.6pt}}{f}[i](x):=p_{i}$ for $x=w_{i}$. We can
see that
$f_{I}=\accentset{\rule{2.79996pt}{0.6pt}}{f}[1]\oplus\accentset{\rule{2.79996pt}{0.6pt}}{f}[2]\oplus\cdots\oplus\accentset{\rule{2.79996pt}{0.6pt}}{f}[m]$.
In our algorithm, since we can not afford to combine the actual profit
functions themselves, we will instead combine monotone point sets and reduce
the combined monotone point sets using Operation 3 whenever necessary.
Definition 4.3 provides us a tool to analyze our algorithm. Every time the
algorithm computes a monotone point set $P$, the set is intended to
approximate some unknown profit function $f$. Our algorithm will make sure
that at any time, $(f,P)$ is $F$-generatable for some set $F$ that can be used
to approximate $f_{I}$ (e.g. $\accentset{\rule{2.79996pt}{0.6pt}}{F}$). Our
goal is to show:

  * •

Correctness: an $F$-generatable $(f,P)$ should be such that $P$ can be used to
approximate $f$.

  * •

Efficiency: if $(f_{a},P_{a})$ and $(f_{b},P_{b})$ are both $F$-generatable,
then there is an efficient way to obtain a $P$ such that $(f_{a}\oplus
f_{b},P)$ is $F$-generatable. This allows us to efficient approximate
$f_{a}\oplus f_{b}$ if both functions are already approximated by $P_{a}$ and
$P_{b}$.

For two functions $\tilde{f}$ and $f$ and a constant $c$, we say that
$\tilde{f}$ $c$-subtractively approximates $f$ if $f$ $c$-additively
approximates $\tilde{f}$. If $\tilde{f}$ $c$-subtractively approximates $f$,
then the function $\hat{f}$ with identical domain as $\tilde{f}$ defined as
$\hat{f}(x):=\tilde{f}(x)-\delta$ $c$-additively approximates $f$. Thus
subtractive approximation is as powerful as additive approximation. The
following shows that individual rounding errors do not accumulate:
lemmalemmageomain Given a set $F$ of profit functions. For any set of $m$
profit functions $\\{f_{1},f_{2},\cdots,f_{m}\\}$ and any set of $m$ monotone
point sets $\\{P_{1},P_{2},\cdots P_{m}\\}$ such that
$(f_{1},P_{1}),(f_{2},P_{2}),\cdots,(f_{m},P_{m})$ are all $F$-generatable,
$(g[P_{1}]\oplus g[P_{2}]\oplus\cdots\oplus g[P_{m}])$ $\delta$-subtractively
approximates $f_{1}\oplus f_{2}\oplus\cdots\oplus f_{m}$.

For efficiency, we will first define a measure of complexity on monotone point
sets. Given two monotone point sets $U=\\{u_{1},u_{2},\cdots,u_{\left\lvert
U\right\rvert}\\}$ and $V=\\{v_{1},v_{2},\cdots,v_{\left\lvert
V\right\rvert}\\}$, if $u_{\left\lvert U\right\rvert}=v_{1}$, define the
concatenation $U\circ V:=\\{u_{1},u_{2},\cdots,u_{\left\lvert
U\right\rvert}=v_{1},v_{2},\cdots v_{\left\lvert V\right\rvert}\\}$. A
monotone point set $P=\\{p_{1},p_{2},\cdots,p_{k}\\}$ is an _upper convex
hull_ if for all $1<i<k$, the point $p_{i}$ is strictly above the line segment
connecting $p_{i-1}$ and $p_{i+1}$. $P$ is a _lower convex hull_ if for all
$1<i<k$, the point $p_{i}$ is strictly below the line segment connecting
$p_{i-1}$ and $p_{i+1}$. A _decomposition_ of monotone point set $P$ into $b$
blocks is a way to write $P=B[1]\circ B[2]\circ\cdots\circ B[b]$ such that
each $B[i]$ is either an upper convex hull or a lower convex hull. For
example, the monotone point set $P=\\{A,B,C,D,E,F,G\\}$ in Fig. 1 can be
decomposed into 3 blocks $P=\\{A,B,C\\}\circ\\{C,D,E,F\\}\circ\\{F,G\\}$,
where $\\{A,B,C\\}$, $\\{C,D,E,F\\}$ are lower convex hulls, and $\\{F,G\\}$
can be considered either an upper convex hull or a lower convex hull.

Given a monotone point set $P=\\{p_{1},p_{2},\cdots,p_{k}\\}$ with no
degenerate point, let $t_{i}$ be $1$ if $p_{i}$ is an apex and $0$ if $p_{i}$
is a base. Let the _convex number_ of $P$ be the number of maximal consecutive
subsequences of $1$’s and $0$’s of the sequence $T=\\{t_{i}\\}$. For example,
for the monotone point set $P=\\{A,B,C,D,E,F,G\\}$ in Fig. 1, we have
$T=\\{1,0,1,0,0,1,1\\}$, which consists of $5$ maximal consecutive
subsequences of $1$’s and $0$’s:
$\\{t_{1}\\},\\{t_{2}\\},\\{t_{3}\\},\\{t_{4},t_{5}\\}$ and
$\\{t_{6},t_{7}\\}$ and thus the convex number of $P$ is $5$. For the relation
between convex number and decomposition, we have the following observation:

######  Observation 4.4.

Let $\tau$ be the convex number of $P$. We have a decomposition into $\tau$
blocks: for $1\leq i\leq k$, there is a block starting from $p_{i}$ for if and
only if $i=1$ or $t_{i}\neq t_{i-1}$.

For example, for the monotone point set $P=\\{A,B,C,D,E,F,G\\}$ in Fig. 1,
this gives the valid decomposition
$P=\\{A,B\\}\circ\\{B,C\\}\circ\\{C,D\\}\circ\\{D,E,F\\}\circ\\{F,G\\}$.

We first show that there is a way to reduce the convex number of a monotone
point set while still being able to approximate the associated profit
function: lemmalemmareduce Fix a set $F$ of profit functions. Suppose $(f,P)$
is $F$-generatable and $P$ contains $l$ points. We can compute another point
set $P^{\prime}$ with a convex number of
$O(({\max}_{y}{P}-{\min}_{y}{P})/\delta)$ in $O(l)$ time such that
$(f,P^{\prime})$ is $F$-generatable.

We say a monotone point set $\hat{P}$ $\sigma$-accurately approximates another
monotone point set if the upper boundary of $R(\hat{P})$ and $R(P)$ match
whenever the y-coordinate is a multiple of $\sigma$, namely if:

  * •

$\left\lfloor{\min}_{y}{\hat{P}}/\sigma\right\rfloor=\left\lfloor{\min}_{y}{P}/\sigma\right\rfloor$
and
$\left\lfloor{\max}_{y}{\hat{P}}/\sigma\right\rfloor=\left\lfloor{\max}_{y}{P}/\sigma\right\rfloor$.

  * •

For every $y\in[{\min}_{y}{P},{\max}_{y}{P}]$ such that $\sigma\mid y$, the
minimum x-coordinate such that $g[P](x)\geq y$ is the same as the minimum
x-coordinate such that $g[\hat{P}](x)\geq y$.

We show that if two monotone point sets have low convex numbers, we can
combine them efficiently: lemmalemmacombine Suppose we have two monotone point
sets $P_{a}$ and $P_{b}$. Suppose the y-coordinates of points in both $P_{a}$
and $P_{b}$ are multiples of $\sigma$ in $[0,l\sigma)$, and suppose both
$P_{a}$ and $P_{b}$ have a convex number of at most $m$. We can compute a set
that $\sigma$-accurately approximates $P_{a}\oplus P_{b}$ in $\tilde{O}(lm)$
time. The problem we are solving here is different from the one in [BL23]
where all blocks must be upper convex hulls555See the part regarding convex
numbers. The definition in the paper is that blocks are lower convex hulls,
but the paper deals with $(\min,+)$-convolution instead of
$(\max,+)$-convolution..

4.4 and 4.4 give us a good way to achieve efficiency: suppose $(f_{a},P_{a})$
and $(f_{b},P_{b})$ are both $F$-generatable for some $F$. We first use 4.4 to
obtain $(f_{a},{P^{\prime}}_{a})$ and $(f_{b},{P^{\prime}}_{b})$ that are both
$F$-generatable where both ${P^{\prime}}_{a}$ and ${P^{\prime}}_{b}$ have low
convex numbers, and then we will 4.4 to obtain
${P^{\prime}}_{a}\oplus{P^{\prime}}_{b}$ ($\sigma$-accurately with regards to
some parameter $\sigma$). By definition, $(f_{a}\oplus
f_{b},{P^{\prime}}_{a}\oplus{P^{\prime}}_{b})$ is $F$-generatable.

With these lemmas, we can prove Lemma 2.3.

###### Proof of Lemma 2.3.

First, we can reduce $\varepsilon$ so that $1/\varepsilon$ becomes an integer.

We can assume $n=2^{K}$ since otherwise we can pad the set with items of very
large weights. For $i=K,K-1,\cdots,0$ in order, we will compute a set of
profit functions $F_{i}=\\{f_{i}[1],f_{i}[2],\cdots,f_{i}[2^{i}]\\}$ such that
each function has values being multiples of $\varepsilon 2^{K-i}$ in
$[0,2^{K-i+1}]$ and that for each $i$, $f_{i}[1]\oplus f_{i}[2]\oplus\cdots
f_{i}[2^{i}]$ $(2\varepsilon n(K-i+1))$-subtractively approximates $f_{I}$ for
$x\in[0,\sum_{j\in I}{w_{j}}]$. By extending the domain of $f_{0}[1]$ to all
$x\geq 0$ trivially we can get a $(2\varepsilon n\log_{2}{n})$-subtractive
approximation of $f_{I}$, which can be made $\varepsilon n$ by lowering the
value of $\varepsilon$ by a logarithmic factor.

For $i=K$, it suffices to let $f_{i}[j]$ be
$\accentset{\rule{2.79996pt}{0.6pt}}{f}[j]$ with values rounded up to
multiples of $\varepsilon$, which introduces a subtractive error of
$n\varepsilon$. The values of $\accentset{\rule{2.79996pt}{0.6pt}}{f}[j]$’s
are contained in $[0,2]$ since $p_{j}\in[1,2]$ for $j\in I$. Since
$1/\varepsilon$ is an integer, we never round a value over $2$, and thus the
values of $f_{i}[j]$’s are contained in $[0,2]$.

Suppose we correctly computed $F_{i+1}$. For each $J\in[1,2^{i+1}]$. Let
$\hat{P}_{i+1}[J]=P(f_{i+1}[J])$. Note that since values of $f_{i+1}[J]$ are
multiples of $\varepsilon 2^{K-i}$ no more than $2^{K-(i+1)+1}$, the
y-coordindates in $\hat{P}_{i}[J]$ are also multiples of $\varepsilon 2^{K-i}$
no more than $2^{K-(i+1)+1}$, and thus $\hat{P}_{i}[J]$ has no more than
$O(2^{K-(i+1)+1}/(2^{K-i}\varepsilon))=O(1/\varepsilon)$ points. We use 4.4 on
each $\hat{P}_{i+1}[J]$ to get ${P^{\prime}}_{i+1}[J]$ with a convex number of
$O(2^{K-(i+1)+1}/\delta))$, which takes total time

$O(2^{i+1}(1/\varepsilon))=O(\varepsilon^{-2}).$

We then use 4.4 to $(\varepsilon 2^{K-(i+1)})$-accurately approximate
$P_{i}[j]={P^{\prime}}_{i+1}[2j-1]\oplus{P^{\prime}}_{i+1}[2j]$ for each
$j\in[1,2^{i}]$ in time

$\tilde{O}(2^{i}\times(1/\varepsilon)\times(2^{K-(i+1)+1}/\delta))=\tilde{O}(2^{k}\varepsilon^{-2}/n)=\tilde{O}(\varepsilon^{-2}).$

We set ${\hat{F}}_{i}=\\{g[P_{i}[1]],g[P_{i}[2]],\cdots,g[P_{i}[2^{i}]]\\}$.
For each $j$, we let $\tilde{f}_{i}[j]=f_{i+1}[2j-1]\oplus f_{i+1}[2j]$. Then
each $(\tilde{f}_{i}[j],P_{i}[j])$ is $F_{i+1}$-generatable. By Definition 4.3
we can see that $g[P_{i}[1]]\oplus g[P_{i}[2]]\oplus\cdots\oplus
g[P_{i}[2^{i}]]$ $\varepsilon n$-subtractively approximates $f_{i}[1]\oplus
f_{i}[2]\oplus\cdots\oplus f_{i}[2^{i}]$. Thus ${\hat{F}}_{i}$ only introduces
an extra additive error of $\varepsilon n$ compared to $F_{i+1}$. To get the
set $F_{i}=\\{f_{i}[1],f_{i}[2],\cdots,f_{i}[2^{i}]\\}$, we round values of
each $g[P_{i}[j]]$ up to multiples of $\varepsilon 2^{K-i}$ to obtain
$f_{i}[j]$, which is possible from a $(\varepsilon 2^{K-(i+1)})$-accurate
approximation of $P_{i}[j]$ since $\varepsilon 2^{K-i}$ is a multiple of
$(\varepsilon 2^{K-(i+1)})$. Such rounding introduces an additive error of at
most $\varepsilon 2^{K-i}\times 2^{i}=\varepsilon n$. The total additive error
for $F_{i}$ is at most:

$2\varepsilon n(K-(i+1)+1)+\varepsilon n+\varepsilon n=2\varepsilon n(K-i+1).$

It is easy to see that

${\max}_{y}{P_{i}[j]}={\max}_{y}{P_{i+1}[2j-1]}+{\max}_{y}{P_{i+1}[2j]}\leq
2^{K-(i+1)+1}\times 2=2^{K-i+1},$

and

${\min}_{x}{P_{i}[j]}={\min}_{x}{P_{i+1}[2j-1]}+{\min}_{x}{P_{i+1}[2j]}\geq
0.$

Thus the values of the function $g[P_{i}[j]]$ are contained in
$[0,2^{K-i+1}]$. Since $1/\varepsilon$ is an integer, we never round a value
over $2^{K-i+1}$. Thus the values of the function $f_{i}[j]$ are also
contained in $[0,2^{K-i+1}]$. Since there are $K=\log_{2}{n}=\tilde{O}(1)$
layers, the total running time is $\tilde{O}(\varepsilon^{-2})$. ∎

####  4.2.3 Proof of Definition 4.3, 4.4 and 4.4

For correctness, we need to prove Definition 4.3: * To derive Definition 4.3,
we need to prove some ingredients.

######  Lemma 4.5.

For any two monotone point sets $P$ and $Q$ with no degenerate points, let
$V=P\oplus Q$. Then for every $v$ on the upper boundary of $R(V)$, $v=p+q$
such that either:

  * •

$p$ is on the upper boundary of $P$ and $q$ is an apex of $Q$, or

  * •

$q$ is on the upper boundary of $Q$ and $p$ is an apex of $P$.

###### Proof.

We know that for every $v$ on the upper boundary of $R(V)$, $v=p+q$ such that
either:

  * •

$p$ is on the upper boundary of $P$ and $q\in Q$, or

  * •

$q$ is on the upper boundary of $Q$ and $p\in P$.

Without loss of generality suppose that $p$ is on the upper boundary of $P$
and $q\in Q$.

If $p$ is an apex of $P$, then since $q$ is on the upper boundary of $Q$, we
are already done. Otherwise, it suffices to show that $q$ is an apex of $Q$.

Since $p$ is not an apex of $P$, we have an infinitesimal segment $e\subset
R(P)$ such that $p$ is strictly contained in $e$. Thus $p+q$ is strictly
contained in $e+q$, which is contained in $R(P)+q$. Suppose that $e$ connects
$p_{l}$ and $p_{r}$ with $p_{l}<p<p_{r}$.

$\mathbf{e+q}$$R(P)+q$$p_{l}+q$$p+q$$p_{r}+q$$p^{\prime}$To $p+q_{l}$To
$p_{r}+q_{l}$ Figure 2: Proof of Lemma 4.5

Figure 2 shows the immediately neighborhood of $p+q$ after zooming into the
infinitesimal segment $e+q$, the shaded region is $R(P)+q$. Suppose $q$ is not
an apex of $Q$, then $q$ is not an endpoint of $Q$. Suppose $q_{l}$ and
$q_{r}$ are the point before and after $q$ in $Q$. The points $p+q_{l}$ and
$p+q_{r}$ can not both be below $e+q$ since otherwise it would make $q$ an
apex of $Q$. Without loss of generality suppose $p+q_{l}$ is above the segment
$e+q$, as shown in the figure. Then a non-zero fraction of the segment
connecting $p_{r}+q_{l}$ and $p_{r}+q$, which is entirely in $R(V)$, is above
$p+q$. Thus as shown in the figure, we can find a point $p^{\prime}$ with
${p^{\prime}}_{x}<p_{x}$ and ${p^{\prime}}_{y}>p_{y}$ on the segment. Since
$p^{\prime}\in R(V)$, $v=p+q$ must not be on the upper boundary of $R(V)$ and
thus must not be in++ $V$, which is a contradiction. ∎

######  Lemma 4.6.

For any two monotone point set $P$ and $Q$ with no degenerate points, if we
let $V=P\oplus Q$, then every apex $v$ of $V$ must be the sum of an apex $p$
of $P$ and an apex $q$ of $Q$.

###### Proof.

Since $v$ is an apex of $V$, it is easy to see that there must not be a non-
degenerate segment (i.e. segment with a length greater than $0$) $e\subset V$
such that $v\in e$.

Suppose $v=p+q$. Suppose $p$ is not an apex of $P$. Then there exists an
infinitesimal segment $e\subset R(P)$ such that $p$ is strictly contained in
$e$. We have a non-degenerate segment $e+q\subset V$ that contains $v=p+q$,
which is a contradiction. Therefore $p$ must be an apex of $P$. Symmetrically,
$q$ must be an apex of $Q$. ∎

######  Lemma 4.7.

For any set $F$ of profit functions, and an $F$-generatable $(f,P)$, we have
the following:

  1. 1.

For every $x$ in the domain of $f$, $g[P](x)\geq f(x)$. Equivalently,
$R(P(f))\subset R(P)$.

  2. 2.

For any apex $p\in P$, $f(p_{x})=p_{y}$.

  3. 3.

For any point $p$ on the upper boundary of $R(P)$, there exist points $a$ and
$b$ $(0\leq a_{y}<b_{y}\leq a_{y}+\delta)$ such that $f(a_{x})\geq
a_{y},f(b_{y})\geq b_{y}$, and $p$ is on the line segment connecting $a$ and
$b$.

###### Proof.

It suffices to argue that each of the three operations in Definition 4.3 does
not introduce new $F$-generatable pairs that violate each of the invariants.

For operation (1), since $P=P(f)$, Invariants (1), (2) are obviously
satisfied. For Invariant (3), since we must have $f(p_{x})\geq p_{y}$, we can
set $a=b=p$.

For operation (2), fix $(f_{a},P_{a})$ and $(f_{b},P_{b})$. Since
$R(P(f_{a}))\subset R(P_{a})$ and $R(P(f_{b}))\subset R(P_{b})$, it is easy to
see that $R(P(f_{a}\oplus f_{b}))\subset R(P_{a})+R(P_{b})=R(P_{a}\oplus
P_{b})$, and therefore invariant (1) must hold. For Invariant (2), suppose a
point $p=(p_{x},p_{y})$ is an apex of $P_{a}\oplus P_{b}$. From Lemma 4.6, $p$
can be expressed as the sum of two apexes $u$ on $P_{a}$ and $v$ on $P_{b}$.
Since $f_{a}(u_{x})=u_{y}$ and $f_{b}(v_{x})=v_{y}$, we must have
$p_{y}=u_{y}+v_{y}=f_{a}(u_{x})+f_{b}(u_{y})\leq(f_{a}\oplus f_{b})(p_{x})$.
Since $p_{y}=g[P](p_{x})\geq(f_{a}\oplus f_{b})(p_{x})$ (from Invariant (1)),
we must have $(f_{a}\oplus f_{b})(p_{x})=p_{y}$. For Invariant (3), let $p$ be
a point on the boundary of $R(P)$, then from Lemma 4.5, $p=u+v$ such that
either $u$ is on the upper boundary of $R(P_{a})$ and $v$ is an apex of
$P_{b}$, or $v$ in on the upper boundary of $R(P_{b})$ and $u$ is an apex of
$P_{a}$. Without loss of generality suppose that $u$ is on the upper boundary
of $R(P_{a})$ and $v$ is an apex of $P_{b}$. Then $f_{b}(v_{x})=v_{y}$
(Invariant (2)). Note that Invariant (3) is satisfied for $(f_{a},P_{a})$. Let
$a_{u}$ and $b_{u}$ be the points in Invariant (3) for $u$ on the upper
boundary of $R(P_{a})$. Then it is not hard to verify that setting
$a:=a_{u}+v$ and $b:=b_{u}+v$ satisfies Invariant (3) for $p$ on the upper
boundary of $R(P)$.

For operation (3), since we only remove non-apexes in $P$ to obtain
$P^{\prime}$, $R(P)\subset R(P^{\prime})=R(\hat{P})$. Therefore $P(f)\subset
R(P)\subset R(\hat{P})$, and thus Invariant (1) must hold. It is easy to see
that no new apexes can be created, and therefore Invariant (2) does not get
broken. Consider Invariant (3) for $\hat{P}$. If $p$ is on the upper boundary
of $P$, then Invariant (3) holds since it holds for $(f,P)$. Otherwise, it is
easy to see that $p$ must be on a segment connecting two apexes $a$ and $b$
with y-coordinates at most $\delta$ apart and it is easy to verify that $a$
and $b$ satisfy Invariant (3) for $p$. ∎

Recall that $\tilde{f}$ $c$-subtractively approximates $f$ if $f$
$c$-additively approximates $\tilde{f}$.

######  Corollary 4.8.

For any set $F$ of profit functions, and an $F$-generatable $(f,P)$, $g[P]$
$\delta$-subtractively approximates $f(x)$.

###### Proof.

We show that for every $x$ in the domain of $f$, we have $g[P](x)-\delta\leq
f(x)\leq g[P](x)$.

$f(x)\leq g[P](x)$ follows from Invariant (1) of Lemma 4.7. To see why
$g[P](x)-\delta\leq f(x)$. Apply Invariant (3) on $(x,g[P](x))$ and obtain $a$
and $b$. Since $a_{y}\leq g[P](x)\leq b_{y}$ and $f$ is non-decreasing, we
have $f(x)\geq f(a_{x})\geq a_{y}\geq b_{y}-\delta\geq g[P](x)-\delta$. ∎

Now we are ready to prove Definition 4.3:

###### Proof.

Since with $m-1$ repetitions of Operation 2 we can $F$-generate $(f_{1}\oplus
f_{2}\oplus\cdots\oplus f_{m},P_{1}\oplus P_{2}\oplus\cdots\oplus P_{m})$,
$g[P_{1}\oplus P_{2}\oplus\cdots\oplus P_{m}]$ $\delta$-subtractively
approximates $f_{1}\oplus f_{2}\oplus\cdots\oplus f_{m}$. It is easy to see
that $g[P_{1}]\oplus g[P_{2}]\oplus\cdots\oplus g[P_{m}]=g[P_{1}\oplus
P_{2}\oplus\cdots\oplus P_{m}]$. Therefore $(g[P_{1}]\oplus
g[P_{2}]\oplus\cdots\oplus g[P_{m}])$ $\delta$-subtractively approximates
$f_{1}\oplus f_{2}\oplus\cdots\oplus f_{m}$. ∎

Now we move on to efficiency and prove 4.4:

###### Proof.

We can obtain $P^{\prime}$ in the following way. Initially set $P^{\prime}=P$.
Scan the apexes in order and store them in a stack. Every time we encounter a
new apex $x$. If the stack is not empty, the top of the stack is $y$, and
$\left\lvert x_{y}-y_{y}\right\rvert\leq\delta$, we can simulate an Operation
3 on $P^{\prime}$ with $x$ and $y$, which involves:

  * •

Removing the vertices between $x$ and $y$ in $P^{\prime}$, and

  * •

If $y$ becomes degenerate, removing $y$ from $P^{\prime}$.

After this, if $y$ is no longer an apex of $P^{\prime}$ or gets removed from
$P^{\prime}$, we remove $y$ from the stack and repeat the procedure above.
Otherwise, we push $x$ to the end of the stack.

After processing each apex $x$, let ${P^{\prime}}_{1\cdots k}$ be the prefix
of $P^{\prime}$ containing the remaining points in $P^{\prime}$ up to $x$. It
is easy to verify that the following two invariants are true:

  * •

No points of ${P^{\prime}}_{1\cdots k}$ are degenerate.

  * •

The stack contains exactly all apexes of ${P^{\prime}}_{1\cdots k}$.

  * •

For every maximal consecutive subsequence of bases in ${P^{\prime}}_{1\cdots
k}$ enclosed by two apexes $a<b$, $b_{y}-a_{y}>\delta$.

The procedure can easily be done in $O(l)$ time, and the resulting
$P^{\prime}$ is clearly $F$-generatable. Since every maximal consecutive
subsequence of bases in ${P^{\prime}}$ is enclosed by two apexes $\delta$ with
a difference larger than $\delta$ in y-coordinates, it is easy to see that
$P^{\prime}$ has a convex number of $O(({\max}_{y}{P}-{\min}_{y}{P})/\delta)$.
∎

Finally, we prove 4.4:

###### Proof.

We can suppose $\sigma=1$ since otherwise we can re-scale all the
y-coordinates. We obtain decompositions $P_{a}=B_{a}[1]\circ
B_{a}[2]\circ\cdots\cdots B_{a}[m_{a}]$ with $m_{a}\leq m$ and
$P_{b}=B_{b}[1]\circ B_{b}[2]\circ\cdots\circ B_{b}[m_{b}]$ with $m_{b}\leq m$
from 4.4.

Suppose that for each two blocks $B_{a}[i]\in P_{a}$ and $B_{b}[j]\in P_{b}$,
we can compute $A[i,j]=B_{a}[i]\oplus B_{b}[j]$. Then by taking the union of
$R(A[i,j])$’s, we get $R(P_{a}\oplus P_{b})$ which can give us $P_{a}\oplus
P_{b}$. The total number of y-coordinates involved in $R(A[i,j])$ does not
exceed
$({\max}_{y}{B_{a}[i]}-{\min}_{y}{B_{a}[i]})+({\max}_{y}{B_{b}[j]}-{\min}_{y}{B_{b}[j]})+2$.
Since we only need a $1$-accurate approximation, to take the union of
$R(A[i,j])$’s, we only need to find the minimum x-coordinate for every
y-coordinate. Therefore every time we take the union with a new $R(A[i,j])$,
we only need to go through all the involved y-coordinates and update the
minimum x-coordinate. For all $R(A[i,j])$’s in total this takes time

$O(\sum_{i,j}{({\max}_{y}{B_{a}[i]}-{\min}_{y}{B_{a}[i]})+({\max}_{y}{B_{b}[j]}-{\min}_{y}{B_{b}[j]})+2})=O(lm).$

We claim that the following claim is true: For two blocks $B_{a}[i]$ and
$B_{b}[j]$ with the total span of y-coordinates being $\mathcal{Y}$,
$B_{a}[i]\oplus B_{b}[j]$ can be computed in $\tilde{O}(\mathcal{Y})$ time.

If the claim is true, then the total running time for computing every $A[i,j]$
is

$\tilde{O}(\sum_{i,j}{({\max}_{y}{B_{a}[i]}-{\min}_{y}{B_{a}[i]})+({\max}_{y}{B_{b}[j]}-{\min}_{y}{B_{b}[j]})+2})=\tilde{O}(lm),$

which finishes the proof of the lemma. Now we prove that for two blocks
$B_{a}[i]$ and $B_{b}[j]$ with the total span of y-coordinates being
$\mathcal{Y}$, we can indeed compute $B_{a}[i]\oplus B_{b}[j]$ in
$\tilde{O}(\mathcal{Y})$ time.

For the case where both $B_{a}[i]$ and $B_{b}[j]$ are upper convex hulls, it
is well known that the Minkowski sum of two convex polygons with $v$ vertices
in total can be computed in $\tilde{O}(v)$ time [dBvKOS00]. Since the number
of vertices is bounded by the number of different y-coordinates, such running
time is sufficient.

It suffices to deal with computations where one of the blocks is a lower
convex hull. Without loss of generality, suppose $B_{a}[i]$ is a lower convex
hull. Let $X={\max}_{y}{B_{a}[i]}-{\min}_{y}{B_{a}[i]}+1$, and
$Y={\max}_{y}{B_{b}[j]}-{\min}_{y}{B_{b}[j]}+1$. We will now introduce a
procedure that computes $B_{a}[i]\oplus B_{b}[j]$ in $\tilde{O}(X+Y)$ time.

Without loss of generality, suppose the y-coordinates of $B_{a}[i]$ span
$[0,X-1]$ and those of $B_{b}[j]$ span $[0,Y-1]$. For $y\in[0,X-1]$, define
$\phi(y)$ as the minimum $x$ with $g[B_{a}[i]](x)\geq y$. For $y\in[0,Y-1]$,
define $\gamma(y)$ as the minimum $x$ with $g[B_{b}[j]](x)\geq y$. It suffices
to compute the convolution

$\eta(y)=\min_{y_{f}\in[0,X-1],y_{g}\in[0,Y-1],y_{f}+y_{g}=y}\phi(y_{f})+\gamma(y_{g}),$

where we know that $\phi$ is convex (i.e. the difference $\phi(y+1)-\phi(y)$
decreases as $y$ increases), in time linear in $X$ and $Y$.

For the computation of $\eta(y)$ for $y\in[0,X-1]$, we use a “reversed”
version of a well-known technique in competitive programming666See e.g.
https://codeforces.com/blog/entry/8219?#comment-139241. We believe that the
reversed version has also been featured in some competitive programming task
in the past, but unfortunately, we could not find a reference.. We treat
values of $\gamma(y)$ where $y>Y-1$ to be $\infty$. We compute $\eta(y)$ in
increasing order of $y$. We have different “candidates” $c$ which we can use
to update $\eta(y)$ with $\phi(y-c)+\gamma(c)$. For two candidates $c_{a}$ and
$c_{b}$ such that $c_{a}<c_{b}$, if
$\phi(y-c_{a})+\gamma(c_{b})<\phi(y-c_{b})+\gamma(c_{b})$, then since
$\phi(y-c_{a})$ increases more slowly than $\phi(y-c_{b})$ as $y$ increases,
$c_{b}$ will never be a better candidate than $c_{a}$777In the more common,
“non-reversed” version, the observation is true for $c_{a}>c_{b}$. Thus a
double-ended queue is used, but here we will use a stack instead. The “non-
reversed” version can also be directly solved using the SMAWK algorithm.. For
two candidates $c_{a}<c_{b}$, we can compute the minimum $\hat{y}$ at which
$\phi(\hat{y}-c_{a})+\gamma(c_{a})<\phi(\hat{y}-c_{b})+\gamma(c_{b})$ (or lack
thereof) by binary search, and such $\hat{y}$ is the “time” when $c_{a}$
becomes better than $c_{b}$. We maintain a stack that stores the candidates
$c_{1}<c_{2}<c_{3}<\cdots<c_{k}$ from bottom to top. We also maintain the
timestamps $t_{1}<t_{2}<\cdots<t_{k-1}$ where $t_{i}$ is the time at which
$c_{i}$ becomes better than $c_{i+1}$, namely the smallest $t_{i}$ such that
$\phi(t_{i}-c_{i})+\gamma(c_{i})<\phi(t_{i}-c_{i+1})+\gamma(c_{i+1})$. After
computing $\eta(y)$ for $y=c$, $c$ becomes available as a new candidate for
future $y$’s. we compute the time $\hat{t}_{k}$ at which the top of the stack
$c_{k}$ becomes better than $c$. If $\hat{t}_{k}\geq t_{k-1}$, then $c_{k}$
can never become the best candidate and we can remove it from the stack. We
repeat until at some $k^{\prime}$ we have
$t_{k^{\prime}-1}<\hat{t}_{k^{\prime}}$ and then add $c$ as $c_{k^{\prime}+1}$
into the stack and set $t_{k^{\prime}}=\hat{t}_{k^{\prime}}$. As each
candidate gets removed at most once, the total running time is $\tilde{O}(X)$.

This algorithm will not work for $y\geq X$ as a candidate $c$ becomes
unavailable when $y-c>X-1$. To deal with this issue, we split integers in
$[0,X+Y-1)$ into consecutive blocks of size $X-1$, where block $k$ contains
integers in $\\{[k(X-1),\min(X+Y-1,(k+1)(X-1)))\\}$. For each $y$, a candidate
$c$ within the same block will always be available. Thus if we call the
procedure above on each block we can cover all pairs of $(y,c)$ in the same
block. It remains to deal with the case where $y$ and $c$ are in adjacent
blocks. To do this, for every two adjacent blocks
$[(k-1)(X-1),k(X-1)),[k(X-1),(k+1)(X-1))$, in decreasing order of
$i=X-2,X-3,\cdots 0$, we compute the contribution of candidates in
$[(k-1)(X-1)+i,k(X-1))$ to $y=k(X-1)+i$ (if $y<X+Y-1$). To do this, we first
add $c=(k-1)(X-1)+i$ to the set of available candidates and then find the best
candidate for $y$ from the set. It is not hard to maintain and find the best
candidate for all $y$’s in near-linear time using the same technique described
before. The total running time is $\tilde{O}(X+Y)$. ∎

##  5 Open Problems

Although this paper closes the gap between the best algorithm and the
conditional lower bound for the Knapsack problem, there are still some open
problems in this field.

  * •

Can we make our algorithm simple? Intuitively, a “simple” algorithm should not
use any results from additive combinatorics, or a technique analogous to
Chan’s number theoretical lemma. Despite the fact that our algorithm for Lemma
2.3 is simple, the reduction to the special case in the proof of Lemma 4.1
requires Lemma 3.9, which uses results from additive combinatorics, as well as
Corollary 3.5, which uses the number theoretical lemma.

  * •

Can we shave an $\Omega(2^{\sqrt{\log^{-1}(1/\varepsilon)}})$ factor from our
algorithm? The previous algorithm from [DJM23] has a running time of
$\tilde{O}\left(n+(\frac{1}{\varepsilon})^{11/5}/2^{\Omega(\sqrt{\log(1/\varepsilon)})}\right)$,
which has such a factor shaved. Moreover, can we establish an equivalence
between $(1-\varepsilon)$-approximation of Knapsack and
$(\min,+)$-convolution? Alternatively, can we prove a stronger conditional
lower bound that rules out such an improvement?

## References

  * [ABHS19] Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay.  SETH-based lower bounds for subset sum and bicriteria path.  In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 41–57, 2019.  doi:10.1137/1.9781611975482.3.
  * [AKM+87] Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber.  Geometric applications of a matrix-searching algorithm.  Algorithmica, 2(1):195–208, November 1987.  doi:10.1007/BF01840359.
  * [BCD+14] David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pǎtraşcu, and Perouz Taslakian.  Necklaces, convolutions, and x+y.  Algorithmica, 69(2):294–314, June 2014.  doi:10.1007/s00453-012-9734-3.
  * [BL23] Cornelius Brand and Alexandra Lassota.  Fast Convolutions for Near-Convex Sequences.  In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms and Computation (ISAAC 2023), volume 283 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:16, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.16, doi:10.4230/LIPIcs.ISAAC.2023.16.
  * [BN21] Karl Bringmann and Vasileios Nakos.  A fine-grained perspective on approximating subset sum and partition.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1797–1815. SIAM, 2021.  doi:10.1137/1.9781611976465.108.
  * [BW21] Karl Bringmann and Philip Wellnitz.  On near-linear-time algorithms for dense subset sum.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 1777–1796. SIAM, 2021.  doi:10.1137/1.9781611976465.107.
  * [Cha18] Timothy M. Chan.  Approximation Schemes for 0-1 Knapsack.  In Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA), pages 5:1–5:12, 2018.  doi:10.4230/OASIcs.SOSA.2018.5.
  * [CMWW19] Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk.  On problems equivalent to (min,+)-convolution.  ACM Trans. Algorithms, 15(1):14:1–14:25, January 2019.  doi:10.1145/3293465.
  * [CW16] Timothy M. Chan and Ryan Williams.  Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1246–1255, 2016.  doi:10.1137/1.9781611974331.ch87.
  * [dBvKOS00] Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf.  Computational Geometry: Algorithms and Applications.  Springer-Verlag, second edition, 2000.  URL: http://www.cs.uu.nl/geobook/.
  * [DJM23] Mingyang Deng, Ce Jin, and Xiao Mao.  Approximating knapsack and partition via dense subset sums.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2961–2979, 2023.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch113, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch113, doi:10.1137/1.9781611977554.ch113.
  * [GL79] George Gens and Eugene Levner.  Computational complexity of approximation algorithms for combinatorial problems.  In Jirí Becvár, editor, Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979, volume 74 of Lecture Notes in Computer Science, pages 292–300. Springer, 1979.  doi:10.1007/3-540-09526-8\\_26.
  * [IK75] Oscar H. Ibarra and Chul E. Kim.  Fast approximation algorithms for the knapsack and sum of subset problems.  Journal of the ACM (JACM), 22(4):463–468, October 1975.  doi:10.1145/321906.321909.
  * [Jin19] Ce Jin.  An improved FPTAS for 0-1 knapsack.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 76:1–76:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.76.
  * [JK18] Klaus Jansen and Stefan E.J. Kraft.  A faster fptas for the unbounded knapsack problem.  European Journal of Combinatorics, 68:148 – 174, 2018.  doi:10.1016/j.ejc.2017.07.016.
  * [Kar72] Richard M Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.
  * [KMPS03] Hans Kellerer, Renata Mansini, Ulrich Pferschy, and Maria Grazia Speranza.  An efficient fully polynomial approximation scheme for the subset-sum problem.  J. Comput. Syst. Sci., 66(2):349–370, 2003.  doi:10.1016/S0022-0000(03)00006-0.
  * [KP04] Hans Kellerer and Ulrich Pferschy.  Improved dynamic programming in connection with an fptas for the knapsack problem.  Journal of Combinatorial Optimization, 8(1):5–11, March 2004.  doi:10.1023/B:JOCO.0000021934.29833.6b.
  * [KPS97] Hans Kellerer, Ulrich Pferschy, and M.Grazia Speranza.  An efficient approximation scheme for the subset-sum problem.  volume 1350, pages 394–403, 12 1997.  doi:10.1007/3-540-63890-3_42.
  * [KPS17] Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider.  On the fine-grained complexity of one-dimensional dynamic programming.  In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 21:1–21:15, 2017.  doi:10.4230/LIPIcs.ICALP.2017.21.
  * [Law79] Eugene L. Lawler.  Fast approximation algorithms for knapsack problems.  Mathematics of Operations Research, 4(4):339–356, 1979.  doi:10.1287/moor.4.4.339.
  * [MWW19] Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk.  Subquadratic approximation scheme for partition.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 70–88, 2019.  doi:10.1137/1.9781611975482.5.
  * [Rhe15] Donguk Rhee.  Faster fully polynomial approximation schemes for knapsack problems.  Master’s thesis, Massachusetts Institute of Technology, 2015.  URL: http://hdl.handle.net/1721.1/98564.
  * [Wil14] Ryan Williams.  Faster all-pairs shortest paths via circuit complexity.  In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 664–673, 2014.  doi:10.1145/2591796.2591811.

##  Appendix A Proof of Lemma 3.9

The following structural lemma follows from Theorem 4.1 and Theorem 4.2 of
Bringmann and Wellnitz [BW21].

######  Lemma A.1.

Let $n$ distinct positive integers
$X=\\{x_{1},\dots,x_{n}\\}\subseteq[\ell,2\ell]$ be given, where
$\ell=o(n^{2}/\log n)$.

Then, for a universal constant $c\geq 1$, for every $c\ell^{2}/n\leq
t\leq\Sigma(X)/2$, there exists $t^{\prime}\in\mathcal{S}(X)$ such that $0\leq
t^{\prime}-t\leq 8\ell/n$.

Now we are ready to prove Lemma 3.9 See 3.9

###### Proof.

If $D(i)<\Delta$, then by the definition of $i$ we have $i=n$, and we can
simply let $\tilde{S}=S$, since $\tilde{p}=0$ always holds. So in the
following we assume $D(i)=\Delta$.

We define $\tilde{S}\subseteq[n]$ as the maximizer of

$\sum_{s\in\tilde{S}\cap[i]}p_{s}+\sum_{s\in\tilde{S}\cap([n]\setminus[i])}(1-\varepsilon)p_{s}$

among all $\tilde{S}$ satisfying $\sum_{s\in\tilde{S}}w_{s}\leq\sum_{s\in
S}w_{s}$ and $\sum_{s\in\tilde{S}}p_{s}\leq\sum_{s\in S}p_{s}$. We claim that
$\tilde{S}$ satisfies the properties (1), (2), (3). Observe that (2), (3)
immediately follow from the definition of $\tilde{S}$. The main part is to
verify (1).

Suppose for contradiction that (1) does not hold. Then, we can find a subset
$K\subseteq\tilde{S}\cap([n]\setminus[i])$ with total profit $p^{*}=\sum_{k\in
K}p_{k}\in(B,B+2]$, which can be obtained by removing items from
$\tilde{S}\cap([n]\setminus[i])$ (recall that each item has profit in
$[1,2)$).

Define item set $I^{\prime}:=[i]\setminus\tilde{S}$. Since
$|\tilde{S}|<\sum_{s\in\tilde{S}}p_{s}/\min_{s\in\tilde{S}}p_{s}\leq\sum_{s\in\tilde{S}}p_{s}\leq\sum_{s\in
S}p_{s}\leq 2m$, by the definition of $D(i)$, we know that $\\{p_{i}:i\in
I^{\prime}\\}$ contains at least $D(i)=\Delta$ distinct elements.

Suppose $c$ is the universal constant in Lemma A.1. We apply Lemma A.1 on the
set of integers $X=\\{p_{i}/\varepsilon:i\in
I^{\prime}\\}\subseteq[1/\varepsilon,2/\varepsilon)$ which contains at least
$\Delta$ distinct integers, where the premise
$1/\varepsilon=o(\Delta^{2}/\log\Delta)$ in Lemma A.1 is satisfied due to the
fact that $\Delta=\omega(\varepsilon^{-1/2}\log^{1/2}{(1/\varepsilon)})$.
Lemma A.1 states that for every
$t\in[c\varepsilon^{-2}/\Delta,0.5\Delta/\varepsilon]$, there exists
$t^{\prime}\in\mathcal{S}(X)$ such that $0\leq t^{\prime}-t\leq
8\varepsilon^{-1}/\Delta$. Here we set

$t:=\frac{(1-\varepsilon)p^{*}}{\varepsilon}+\frac{\varepsilon^{-1}}{\Delta},$

which satisfies
$t>p^{*}(1-\varepsilon)/\varepsilon>(1-\varepsilon)B/\varepsilon=(1-\varepsilon)(9c\varepsilon^{-1}/\Delta)/\varepsilon>c\varepsilon^{-2}/\Delta$,
and
$t<(B+2)/\varepsilon+\varepsilon^{-1}/\Delta=9c\varepsilon^{-2}/\Delta+2/\varepsilon+\varepsilon^{-1}/\Delta\leq
o(\varepsilon^{-3/2}\log^{-1/2}(1/\varepsilon))\leq 0.5\Delta/\varepsilon$.
Then the conclusion of Lemma A.1 says that there is a subset $R\subseteq
I^{\prime}$ of items with total profit $\tilde{p}:=\varepsilon\cdot
t^{\prime}$, satisfying

$1/\Delta\leq\tilde{p}-p^{*}(1-\varepsilon)\leq 9/\Delta.$ (4)

Note that (4) implies

$\displaystyle p^{*}-\tilde{p}$ $\displaystyle\geq\varepsilon\cdot
p^{*}-9/\Delta$ $\displaystyle>\varepsilon\cdot B-9/\Delta$
$\displaystyle=\varepsilon\cdot 9c\varepsilon^{-1}/\Delta-9/\Delta$
$\displaystyle\geq 0.$

Recall that $R\subseteq I^{\prime}=[i]\setminus\tilde{S}$ and
$K\subseteq\tilde{S}\cap([n]\setminus[i])$, which must both be non-empty.
Since the efficiency of items are sorted in non-increasing order, we have
$\min_{r\in R}p_{r}/w_{r}\geq\max_{k\in K}p_{k}/w_{k}$. Now we define the set
of items

$\tilde{S}^{\prime}:=(\tilde{S}\setminus K)\cup R.$

Then, we have

$\displaystyle\sum_{s\in\tilde{S}}p_{s}-\sum_{s\in\tilde{S}^{\prime}}p_{s}$
$\displaystyle=\sum_{k\in K}p_{k}-\sum_{r\in R}p_{r}$
$\displaystyle=p^{*}-\tilde{p}$ $\displaystyle\geq 0,$

and

$\displaystyle\sum_{s\in\tilde{S}}w_{s}-\sum_{s\in\tilde{S}^{\prime}}w_{s}$
$\displaystyle=\sum_{k\in K}w_{k}-\sum_{r\in R}w_{r}$
$\displaystyle\geq\frac{\sum_{k\in K}p_{k}}{\max_{k\in
K}(p_{k}/w_{k})}-\frac{\sum_{r\in R}p_{r}}{\min_{r\in R}(p_{r}/w_{r})}$
$\displaystyle\geq\frac{1}{\min_{r\in R}(p_{r}/w_{r})}\cdot\left(\sum_{k\in
K}p_{k}-\sum_{r\in R}p_{r}\right)$ $\displaystyle=\frac{1}{\min_{r\in
R}(p_{r}/w_{r})}\cdot\left(p^{*}-\tilde{p}\right)$ $\displaystyle\geq 0.$

Hence, $\sum_{s\in\tilde{S}^{\prime}}p_{s}\leq\sum_{s\in\tilde{S}}p_{s}$ and
$\sum_{s\in\tilde{S}^{\prime}}w_{s}\leq\sum_{s\in\tilde{S}}w_{s}$. On the
other hand, by (4), we know that

$\displaystyle\left(\sum_{s\in\tilde{S}^{\prime}\cap[i]}p_{s}+\sum_{s\in\tilde{S}^{\prime}\cap([n]\setminus[i])}(1-\varepsilon)p_{s}\right)-\left(\sum_{s\in\tilde{S}\cap[i]}p_{s}+\sum_{s\in\tilde{S}\cap([n]\setminus[i])}(1-\varepsilon)p_{s}\right)$
$\displaystyle=\ $ $\displaystyle\sum_{r\in R}p_{r}-\sum_{k\in
K}(1-\varepsilon)p_{k}$ $\displaystyle=\ $
$\displaystyle\tilde{p}-(1-\varepsilon)p^{*}$ $\displaystyle\geq\ $
$\displaystyle 1/\Delta>0,$

contradicting the definition of $\tilde{S}$ being a maximizer.

Hence, we have established that $\tilde{S}$ satisfies (1). ∎

##  Appendix B Proof of Lemma 3.1

Recall that we defined the following simpler problem. See 2

See 3.1

###### Proof.

First, we can reduce $\varepsilon$ so that $1/\varepsilon$ becomes an integer.

We will restrict the profit values into small intervals, as follows: divide
the items into $O(\log\frac{\max_{j}p_{j}}{\min_{j}p_{j}})=$
$O(\log\varepsilon^{-1})$ groups (see Section 2.2), each containing items with
$p_{i}\in[2^{j},2^{j+1}]$ for some $j$ (which can be rescaled to $[1,2]$).
Finally, use the merging lemma Lemma 3.2 to merge the profit functions of all
groups, in $\tilde{O}(n+\varepsilon^{-2})$ overall time.

Now, having restricted the profit values into $[1,2)$, we can round every
profit value to a multiple of $\varepsilon$, which incurs only
$(1-O(\varepsilon))$ approximation factor in total.

Finally, the following greedy lemma takes care of the case with total profit
above $\Omega(\varepsilon^{-1})$.

######  Lemma B.1.

Suppose $p_{i}\in[1,2]$ for all $i\in I$. For $B=\Omega(\varepsilon^{-1})$,
the profit function $f_{I}$ can be approximated with additive error
$O(\varepsilon B)$ in $O(n\log n)$ time.

###### Proof.

Simply sort the items in nonincreasing order of efficiency $p_{i}/w_{i}$, and
define the profit function $\tilde{f}$ resulting from greedy, with function
values $0,p_{1},p_{1}+p_{2},\dots,p_{1}+\dots+p_{n}$ and $x$-breakpoints
$0,w_{1},w_{1}+w_{2},\dots,w_{1}+\dots+w_{n}$. It clearly approximates $f_{I}$
with an additive error of $\max_{i}p_{i}\leq 2\leq O(\varepsilon B)$ for
$B=\Omega(\varepsilon^{-1})$. ∎

This greedy approach achieves $(1-O(\varepsilon))$-approximation for large
profit values. Hence, it is sufficient to approximate $f_{I}$ up to
$2/\varepsilon$. ∎