Weakly Approximating Knapsack in Subquadratic Time

In the Knapsack problem, one is given a knapsack of capacity $t$ and a set of $n$ items. Each item $i$ has a weight $w_i$ and a profit $p_i$. The goal is to select a subset of items such that their total weight does not exceed $t$, and their total profit is maximized.

Knapsack is one of Karp’s 21 NP-complete problems [26], which motivates the study of approximation algorithms. In particular, it is well known that Knapsack admits fully polynomial-time approximation schemes (FPTASes), which can return a feasible solution with a total profit of at least $\mathrm{OPT}/(1+\epsilon )$ in $\mathrm{poly}(n,\frac{1}{\epsilon })$ time. (We use $\mathrm{OPT}$ to denote the maximum total profit one can achieve using capacity $t$.) There has been a long line of research on designing faster FPTASes for Knapsack [21, 33, 29, 37, 10, 24, 18, 15, 34]. Very recently, Chen, Lian, Mao and Zhang [15] and Mao [34] indenpendently obtained $\tilde{O}(n+{(\frac{1}{\epsilon })}^2)$-time FPTASes¹¹1In the paper, we use an $\tilde{O}(\cdot )$ notation to hide polylogarithmic factors in $n$ and $\frac{1}{\epsilon }$.. On the negative side, there is no $O({(n+\frac{1}{\epsilon })}^{2-\delta })$-time FPTAS for any constant $\delta >0$ assuming $(\min ,+)$-convolution cannot be solved in subquadratic time [17, 32]. Hence, further improvement on FPTASs for Knapsack seems hopeless unless the $(\min ,+)$-convolution conjecture is overturned. Due to the symmetry of weight and profit, the same upper and lower bounds also hold if we seek a solution of total profit at least $\mathrm{OPT}$, but relax the capacity to $(1+\epsilon )t$. In this paper, we consider weak approximation schemes, which relax both the total profit and the capacity. More precisely, a weak approximation scheme seeks a subset of items with total weight at most $(1+\epsilon )t$ and total profit at least $\mathrm{OPT}/(1+\epsilon )$.

Weak approximation algorithms are commonly studied in the context of resource augmentation (see e.g., [20, 22]). One often resorts to resource augmentation when there is a barrier to further improvement on standard (i.e., non-weak) approximation algorithms. The two most relevant examples are Subset Sum and Unbounded Knapsack. Both problems admit an $\tilde{O}(n+{(\frac{1}{\epsilon })}^2)$-time FPTAS [27, 9, 23], while an $O({(n+\frac{1}{\epsilon })}^{2-\delta })$-time FPTAS has been ruled out assuming the $(\min ,+)$-convolution conjecture [32, 17, 35, 9]. Their weak approximation, however, can be done in truly subquadratic time. For Subset Sum, Mucha, Węgrzycki and Włodarczyk [35] showed a $O(n+{(\frac{1}{\epsilon })}^{5/3})$-time weak approximation scheme, and very recently, Chen et al. [13] further improved the running time to $\tilde{O}(n+\frac{1}{\epsilon })$-time. For Unbounded Knapsack, Bringmann and Cassis [6] established an $\tilde{O}(n+{(\frac{1}{\epsilon })}^{3/2})$-time weak approximation scheme. Given that the standard approximation of Knapsack has been in a similar situation, it is natural to ask whether the weak approximation of Knapsack can be done in truly subquadratic time.

It is worth mentioning that weak approximation schemes for Subset Sum and Unbounded Knapsack are not straightforward extensions of the existing standard (non-weak) approximation schemes. The first truly subquadratic-time weak approximation scheme for Subset Sum [35] as well as its recent improvement [13] both rely on a novel application of additive combinatorics, and the first truly subquadratic-time weak approximation scheme for Unbounded Knapsack [6] relies on a breakthrough on bounded monotone $(\min ,+)$-convolution [11, 16]. Unfortunately, techniques developed in these prior papers are not sufficient to obtain a truly subquadratic-time weak approximation scheme for Knapsack.

We assume that $\epsilon ⩽1$, since otherwise we can approximate using a linear-time 2-approximation algorithm for Knapsack [30, Section 2.5]. We denote the set of real numbers between $a$ and $b$ as $[a,b]$. All logarithms are based $2$.

To ease the presentation of our algorithm, we interpret Knapsack from the perspective of tuples. An item can be regarded as a tuple $(w,p)$, where $w$ and $p$ represent the weight and profit, respectively. Throughout the paper, we do not distinguish an item and a tuple, and always refer to the first entry as weight and the second entry as profit. The efficiency of a tuple $(w,p)$ is defined to be its profit-to-weight ratio $\frac{p}{w}$. The efficiency of $(0,0)$ is defined to be $0$.

Let $I$ be a multiset of tuples. We use $w(I)$ to denote the total weight of tuples in $I$. That is, $w(I)={\sum }_{(w,p)\in I}w$. Similarly, we define $p(I)={\sum }_{(w,p)\in I}p$. Define the set of all (2-dimensional) subset sums of $I$ as follows:

Every tuple $(w,p)\in 𝒮(I)$ corresponds to a Knapsack solution with total weight $w$ and total profit $p$. We say a tuple $(w,p)$ dominates another tuple $(w^{\prime },p^{\prime })$ if $w⩽w^{\prime }$, $p⩾p^{\prime }$, and at least one of the two inequalities holds strictly. Let ${𝒮}^{+}(I)$ be the set obtained from $𝒮(I)$ by removing all dominated tuples. Every tuple in ${𝒮}^{+}(I)$ corresponds to a Pareto optimal solution for Knapsack, and vice versa. Let $t$ be the given capacity. Knapsack can be formulated as follows:

We consider the more general problem of (weakly) approximating ${𝒮}^{+}(I)$.

When $S^{\prime }$ approximates a set $S$ that contains only one tuple $(w,p)$, we also say that $S^{\prime }$ approximates the tuple $(w,p)$.

Let $(I,t)$ be a Knapsack instance. Let $\mathrm{OPT}$ be the optimal value. Our goal is to compute a set $S^{\prime }$ such that

• $\mathrm{■}$

  $S^{\prime }$ approximates ${𝒮}^{+}(I)\cap ([0,t]\times [0,OPT])$ with additive error $(\epsilon t,\epsilon \cdot \mathrm{OPT})$ and

• $\mathrm{■}$

  $S^{\prime }$ is dominated by $𝒮(I)$.

The former ensures that $S^{\prime }$ provides a good (weak) approximation of the optimal solution, and the latter ensures that every tuple in $S^{\prime }$ is not better than a true solution. Our definition is essentially the same as that by Bringmann and Cassis [6], albeit their definition is for sequences.

Let $I_1\cup I_2$ be a partition of $I$. It is easy to observe the following.

• $\mathrm{■}$

  $𝒮(I)=𝒮(I_1)+𝒮(I_2)$, where the sumset $X+Y$ is defined by the following formula.

  $$X+Y=\{(w_1+w_2,p_1+p_2)\text{ : }(w_1,p_1)\in X\text{ and }(w_2,p_2)\in Y\};$$

• $\mathrm{■}$

  ${𝒮}^{+}(I)={𝒮}^{+}(I_1)\oplus {𝒮}^{+}(I_2),$ where $\oplus$ represents the $(\max ,+)$-convolution defined by the following formula.

  $$X\oplus Y=\{(w,p)\in X+Y\text{ : }(w,p)\text{ is not dominated in }X+Y\}.$$

Using Chi et al.’s $\tilde{O}(n^{3/2})$-time algorithm for bounded monotone $(\min ,+)$-convolution [16] and Bringmann and Cassis’s algorithm for approximating the $(\max ,+)$-convolution [6, Lemma 28 in the full version], we can approximate the $(\max ,+)$-convolution of two sets in $\tilde{O}({(\frac{1}{\epsilon })}^{3/2})$ time. Using the divide-and-conquer approach from [10], we can generalize it to multiple sets. The proof of the following lemma can be found in the appendix of the full version.

With Lemma 3, we can approximate ${𝒮}^{+}(I)\cap ([0,t]\times [0,OPT])$ as follows. Partition $I$ into several groups, approximate each group independently, and merge their results using Lemma 3. As long as there are not too many groups, the merging time will be subquadratic. The following lemmas explain how the multiplicative factor and additive error accumulate during the computation. Their proofs can be found in the full version.

In the rest of the paper, we may switch between the multiplicative factor and the additive error, although our goal is to bound the latter. It is helpful to keep the following observation in mind.

With Lemma 3, we can reduce the problem of weakly approximating Knapsack to the following problem.

The reduced problem $\mathrm{RP}(\alpha )$: given a set $I$ of $n$ items from $[1,2]\times [1,2]$ and a real number $\alpha \in [\frac{1}{2},\frac{1}{4\epsilon }]$, compute a set $S$ of size $\tilde{O}(\frac{1}{\epsilon })$ that approximates ${𝒮}^{+}(I)\cap ([0,\frac{1}{\alpha \epsilon }]\times [0,\frac{1}{\alpha \epsilon }])$ with additive error $(O(\frac{1}{\alpha }),O(\frac{1}{\alpha }))$. Moreover, $S$ should be dominated by $𝒮(I)$.

The approach to reducing the problem is similar to that in [15]. The details of the proof can be found in the full version.

Throughout the rest of the paper, we write ${𝒮}^{+}(I)\cap ([0,\frac{1}{\alpha \epsilon }]\times [0,\frac{1}{\alpha \epsilon }])$ as ${𝒮}^{+}(I;\frac{1}{\alpha \epsilon })$ for short, and when the weight and profit both have an additive error of $\delta$, we simply say that additive error is $\delta$.

We also remark that when presenting algorithms for the reduced problem $\mathrm{RP}(\alpha )$, we will omit the requirement that the resulting set $S$ should be dominated by $𝒮(I)$ since it is guaranteed by the algorithms in a quite straightforward way. More specifically, in those algorithms (including Lemma 3), rounding is the only place that may incur approximation errors, and whenever we round a tuple $(w,p)$, we always round $w$ up and round $p$ down. As a consequence, a set after rounding is always dominated by the original set.

We present a few results that will be used by our algorithm as subroutines.

To illustrate our main idea, we first present a simpler algorithm that runs in $\tilde{O}(n+{(\frac{1}{\epsilon })}^{11/6})$ time. When $\alpha ⩾{(\frac{1}{\epsilon })}^{2/3}$, the algorithm in Lemma 8 already runs in $\tilde{O}(n+{(\frac{1}{\epsilon })}^{11/6})$ time. It remains to consider the case where $\frac{1}{2}⩽\alpha ⩽{(\frac{1}{\epsilon })}^{2/3}$. In the rest of this section, we assume that $I=\{(w_1,p_1),\mathrm{\dots },(w_n,p_n)\}$ and that $\frac{p_1}{w_1}⩾\mathrm{\cdots }⩾\frac{p_n}{w_n}$.

Let $\tau$ be a parameter that will be specified later. We first partition $I$ into groups as follows. For the items $(w_1,p_1),\mathrm{\dots },(w_n,p_n)$ in $I$, we bundle every $\tau$ items as a group until we obtain $\lceil \frac{1}{\alpha \epsilon \tau }\rceil +1$ groups. For the remaining items, say $\{(w_i,p_i),\mathrm{\dots },(w_n,p_n)\}$, we further divide them into two groups $\{(w_i,p_i),\mathrm{\dots },(w_{i^{\prime }},p_{i^{\prime }})\}$ and $\{(w_{i^{\prime }+1},p_{i^{\prime }+1}),\mathrm{\dots },(w_n,p_n)\}$, where $i^{\prime }$ is the maximum index such that $\frac{p_i}{w_i}-\frac{p_{i^{\prime }}}{w_{i^{\prime }}}⩽\frac{1}{\tau }$. At the end, we obtain $m=\lceil \frac{1}{\alpha \epsilon \tau }\rceil +3$ groups $I_1,I_2,\mathrm{\dots },I_m$. For simplicity, we assume that none of these groups is empty. This assumption is without loss of generality, since empty groups only make things easier.

For each group $I_j$, we define ${\mathrm{\Delta }}_j$ to be the maximum difference between the efficiencies of the items in $I_j$. That is,

By the way we construct the groups, we have that ${\sum }_j{\mathrm{\Delta }}_j⩽\frac{3}{2}$.

We say a group $I_j$ is good if ${\mathrm{\Delta }}_j⩽\frac{1}{\tau }$, and bad otherwise.

Note that the efficiency of any item in $I$ is within the range $[\frac{1}{2},2]$. For each good group $I_j$, its item efficiencies are in the range $[\rho ,\rho +\frac{1}{\tau }]$ for some constant $\rho \in [\frac{1}{2},2]$, so we can compute a set $S_j$ of $\tilde{O}(\frac{1}{\epsilon })$ that approximates each tuple $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $(\epsilon w,\epsilon p)$ via Corollary 12 in $O(|I_j|+\frac{1}{\epsilon }+{(\frac{1}{\epsilon })}^2\frac{1}{\tau })$ time. Since the items are from $[1,2]\times [1,2]$, for any tuple in ${𝒮}^{+}(I_j)$, its weight and profit are of the same magnitude, so are the corresponding additive errors. We can say that $S_j$ approximates each tuple $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $O(\epsilon w)$.

For bad groups, we shall approximate them less accurately: we shall use $\frac{1}{\alpha \tau }$ instead of $\epsilon$ as the accuracy parameter. (Later we will show that we can still obtain a good bound on the total additive error using the proximity bound in Lemma 9.) We compute a set $S_j^{\prime }$ of size $\tilde{O}(\alpha \tau )$ that approximates each tuple $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $(\frac{w}{\alpha \tau },\frac{p}{\alpha \tau })$ via Corollary 12 in $O(|I_j|+\alpha \tau +{\alpha }^2{\tau }^2{\mathrm{\Delta }}_j)$ time. We also compute a set $S_j^{\prime \prime }$ of size $\tilde{O}(\alpha \tau )$ that approximates each $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $(\frac{w(I)-w}{\alpha \tau },\frac{p(I)-p}{\alpha \tau })$ via Corollary 13 in $O(|I_j|+\alpha \tau +{\alpha }^2{\tau }^2{\mathrm{\Delta }}_j)$ time. Again, since the weight and the profit are of the same magnitude, we can say that $S_j^{\prime }$ approximates each tuple $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $O(\frac{1}{\alpha \tau }\cdot w)$, and that $S_j^{\prime \prime }$ approximates each tuple $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $O(\frac{1}{\alpha \tau }\cdot (w(I)-w))$. Now consider the set $S_j=S_j^{\prime }\cup S_j^{\prime \prime }$. One can verify that $S_j$ approximates each tuple $(w,p)\in {𝒮}^{+}(I_j)$ with additive error $O(\frac{1}{\alpha \tau }\cdot \min \{w,(w(I)-w)\})$.

The last step is to compute a set $S$ of size $\tilde{O}(\frac{1}{\epsilon })$ that approximates $S_1\oplus \mathrm{\cdots }\oplus S_m$ with factor $1+O(\epsilon )$ via Lemma 3. Note that each set $S_j$ is of size $\tilde{O}(\frac{1}{\epsilon })$ or $\tilde{O}(\alpha \tau )$. This step takes time $\tilde{O}(\frac{m}{\epsilon }+m\alpha \tau +{(\frac{1}{\epsilon })}^{3/2}m)$.