Approximating Partition in Near-Linear Time

Theorem 1 immediately implies the following theorem since any weak approximation scheme for Subset Sum is a strong approximation scheme for Partition.

Both of the above two results match (up to a polylogarithmic factor) the lower bound of $(n+\frac{1}{\varepsilon})^{1-o(1)}$. To our best knowledge, Partition is the first NP-hard problem that admits an FPTAS that is near-linear in both $n$ and $1/\varepsilon$. We also remark that our weak approximation scheme for Subset Sum generalizes Bringmann’s $\widetilde{O}(n+t)$-time exact algorithm for Subset Sum [Bri17] in the sense that when $\varepsilon:=\frac{1}{2t}$, the weak approximation scheme becomes an exact algorithm with $\widetilde{O}(n+t)$ running time.

To attain Theorem 1, we utilize an additive combinatorics result that is different from the ones previously used in Subset Sum and Knapsack [GM91, MWW19, BN20, BW21, WC22, DJM23, CLMZ24]. We believe that it may be of independent interest.

Let $X=\{x_{1},\ldots,x_{n}\}$. Solving Subset Sum can be reduced to computing the sumset $\{x_{1},0\}+\cdots+\{x_{n},0\}$. Our main technique is an approach for efficiently approximating (a major part of) the sumset of integer sets, which can be seen as a combination of a deterministic sparse convolution [BFN22] (see Lemma 5) and an additive combinatorics result from Szemerédi and Vu [SV05] (see Theorem 14). We briefly explain the idea below.

Suppose that we are to compute the sumset of $A_{1},\ldots,A_{\ell}$. We compute it in a tree-like manner. $A_{1},\ldots,A_{\ell}$ forms the bottom level of the tree. We compute the next level by taking the sumset of every two nodes in the bottom level. That is, we compute $A_{1}+A_{2},A_{3}+A_{4},\ldots,A_{\ell-1}+A_{\ell}$. Let $B_{i}=A_{2i-1}+A_{2i}$ for $i=1,\ldots,\ell/2$. If $B_{1},\ldots,B_{\ell/2}$ have small total sizes, then we can compute all of them efficiently via sparse convolution, and proceed to the next round. When $B_{1},\ldots,B_{\ell/2}$ has a large total size, we cannot afford to compute them. Instead, we utilize an additive combinatorics result from Szemerédi and Vu [SV05] to show that $A_{1}+\cdots+A_{\ell}$ has a long arithmetic progression. We will further show that this arithmetic progression can be extended to a long sequence with small differences between consecutive terms. Given the existence of such a long sequence, we can directly compute a set that nicely approximates (a major part of) $A_{1}+\cdots+A_{\ell}$.

Besides sparse convolution and the additive combinatorics result, the following techniques are also essential for obtaining a near-linear running time.

• •

  Recall that we compute a level only when it has a small total size. Therefore, we should estimate the size of a level without actually computing it. The estimation can be done by utilizing the sparse convolution algorithm [BFN22].

• •

  The additive combinatorics result [SV05] only guarantees the existence of a long arithmetic progression, and is non-constructive. Therefore, we can only obtain a good approximation of solution values, but may not be able to recover solutions efficiently. A similar issue also arises in the algorithm for dense Subset Sum [BW21]. In Section 4, we show the issue can be fixed in an approximate sense.

• •

  Rounding is necessary every time when we compute a new level. If the tree has too many levels, then the error caused by rounding would accumulate and become far more than what is acceptable. To ensure a small number of tree levels, we use the color-coding technique, which was proposed by Bringmann [Bri17] to design exact algorithms for Subset Sum. For technical reasons, the color-coding technique is slightly modified to ensure additional properties.

Our algorithm, and in particular, the usage of arithmetic progression, is inspired by the dense Subset Sum algorithm by Bringmann and Wellnitz [BW21], and Galil and Margalit [GM91], but we obtain the arithmetic progression in a way that is different from these two works. Bringmann and Wellnitz [BW21], and Galil and Margalit [GM91] got the arithmetic progression via an additive combinatorics result saying that if an integer set $A$ has $\widetilde{\Omega}(\sqrt{u})$ distinct integers, where $u$ is the maximum integer in $A$, then the collection of subset sums of $A$ must contain an arithmetic progression of length ${\Omega}(u)$ (see, e.g., [Sár94]). In contrast, we use a different result from additive combinatorics, which states that if we have $\ell$ sets $A_{1},\ldots,A_{\ell}$ of size at least $k$ and $\ell k\geqslant\Omega(u)$, then $A_{1}+\cdots+A_{\ell}$ must contain an arithmetic progression of length ${\Omega}(u)$.

Subset Sum is a special case of Knapsack. There is a long line of research on approximation schemes for Knapsack, e.g., [IK75, Kar75, Law79, KP04, Rhe15, Cha18, Jin19, DJM23]. There is a conditional lower bound of $(n+1/\varepsilon)^{2-o(1)}$ based on the (min, +)-convolution hypothesis[CMWW19, KPS17]. Very recently, [CLMZ23] and [Mao23] establish an $\widetilde{O}(n+1/\varepsilon^{2})$-time FPTAS for Knapsack, independently.

In addition to approximation algorithms, exact pseudopolynomial-time algorithms for Knapsack and Subset Sum have also received extensive studies in recent years, e.g., [Bri17, AT19, PRW21, BC23, CLMZ24, Bri23, Jin23]. It is worth mentioning that there is an algorithm [BN20] with running time $\widetilde{O}({k^{4/3}})$ for Subset Sum where $k$ is the number of subset sums that are smaller than $t$, which shares a similar flavor to our algorithm in the sense that it combines sparse convolution and Ruzsa’s triangle inequality for sumset estimation (which is a different result in additive combinatorics).

Our algorithm utilizes sparse convolution algorithms, see, e.g., [CH02, AR15, CL15, Nak20, BFN21, BN21a, BFN22]. We also adopt results from additive combinatorics, see, e.g., [Alo87, Sár89, Sár94, SV05, SV06]. Additive combinatorics results have been exploited extensively in recent years on Knapsack and Subset Sum, see, e.g., [GM91, MWW19, BN20, BW21, WC22, DJM23, CLMZ24].

In Section 2, we introduce some necessary terminology and tools, and show that it suffices to solve a reduced problem. In Section 3, we present a near-linear-time algorithm for approximating optimal values. We further show how to recover an approximate solution in near-linear time in Section 4. Section 5 concludes the paper. All the omitted proofs can be found in the appendices.

Throughout this paper, we assume that $\varepsilon>0$ is sufficiently small. We also assume that $\frac{1}{\varepsilon}$ is an integer by adjusting $\varepsilon$ by an $O(1)$ factor. All logarithms ($\log$) in this paper are base $2$.

Let $w,v$ be two real numbers. We use $[w,v]$ to denote the set of integers between $w$ and $u$. That is, $[w,v]=\{z\in\mathbb{Z}:w\leqslant z\leqslant v\}$. Let $Y$ be a nonempty set of integers. We write $Y\cap[w,v]$ as $Y[w,v]$. We denote the minimum and maximum elements of $Y$ by $\min(Y)$ and $\max(Y)$, respectively. We write $\sum_{y\in Y}y$ as $\Sigma(Y)$. We refer to the number of elements in $Y$ as the size of $Y$, denoted by $|Y|$. Through this paper, we use both the terms “set” and “multi-set”. Only when the term “multi-set” is explicitly used do we allow duplicate elements. Unless otherwise stated, a subset of a multi-set is a multi-set.

Let $(X,t)$ be an arbitrary Subset Sum instance. We assume that $x\leqslant t$ for any $x\in X$ since the integers greater than $t$ can be safely removed from $X$. We define ${\cal S}_{X}$ to be the set of all subset sums of $X$. That is, ${\cal S}_{X}=\{\Sigma(Y):Y\subseteq X\}$. Subset Sum actually asks for the maximum element of ${\cal S}_{X}[0,t]$.

We consider the more general problem of approximating ${\cal S}_{X}$.

Our algorithm has two phases. In the first phase, it computes a set $\widetilde{S}$ that approximates ${\cal S}_{X}[0,t]$ with additive error $\varepsilon t$. Let $\tilde{s}$ be the maximum element of $\widetilde{S}[0,(1+\varepsilon)t]$. Clearly, $\tilde{s}\leqslant(1+\varepsilon)t$. Definition 3(i) implies that $\tilde{s}\geqslant\Sigma(Y^{*})-\varepsilon t$, and Definition 3(ii) implies that there exists $Y\subseteq X$ such that $\tilde{s}-\varepsilon t\leqslant\Sigma(Y)\leqslant\tilde{s}+\varepsilon t$. Therefore,

The first inequality is due to the fact that we can assume the optimal objective value $\Sigma(Y^{*})\geqslant t/2$³³3If $\Sigma(Y^{*})<t/2$, every interger in $X$ must be less than $t/2$. Then it implies that $Y^{*}=X$ because otherwise, we can improve $Y^{*}$ by selecting one more integer in $X$. Such an instance can be solved trivially in $O(n)$ time.. By adjusting $\varepsilon$ by a factor of $4$, we have that

The second phase of the algorithm recovers such a $Y$ from $\tilde{s}$.

Let $(X_{1},X_{2})$ be a partition of $X$. We have ${\cal S}_{X}={\cal S}_{X_{1}}+{\cal S}_{X_{2}}$, where the sum of two sets is defined by the following.

The set $A+B$ is called the sumset of $A$ and $B$. It is well-known that the sumset of two integer sets can be computed via the classical convolution algorithm based on Fast Fourier Transformation (FFT).

When the sumset has a small size, sparse convolution algorithms whose running time is linear in the output size may be used. Although there are faster randomized algorithms, to ease the analysis, we use the following deterministic algorithm due to Bringmann, Fischer, and Nakos [BFN22].

Lemma 4 immediately implies a few simple approaches for approximating the sumset of two sets.

We can reduce our task to the following problem $\mathrm{RP}(\beta)$ where $\beta\in[1,\frac{1}{\varepsilon}]$ be an integer.

The proof of the following lemma is deferred to Appendix A. Basically, we can preprocess the instance to get rid of tiny integers less than $\varepsilon t$. Then we scale the instance by $\varepsilon^{2}t$. After that, all integers in $X$ are within $[\frac{1}{\varepsilon},\frac{1}{\varepsilon^{2}}]$. Then we partition $X$ into $\log\frac{1}{\varepsilon}$ groups so that the integers within the same group differ by a factor of at most $2$. We deal with each group separately and merge their results by Lemma 6. By further scaling, we can assume that $x\in[\frac{1}{\varepsilon},\frac{2}{\varepsilon}]$ for each group.

In what follows, we present an algorithm for part (i) of the reduced problem $\mathrm{RP}(\beta)$ in Section 3, and an algorithm for part (ii) in Section 4.

Recall that our goal is to approximate ${\cal S}_{X}[\frac{\beta}{\varepsilon},\frac{2\beta}{\varepsilon}]$ and that $x\in[\frac{1}{\varepsilon},\frac{2}{\varepsilon}]$ for any $x\in X$. For any $Y\subseteq X$ with $\Sigma(Y)\in{\cal S}_{X}[\frac{\beta}{\varepsilon},\frac{2\beta}{\varepsilon}]$, we have $|Y|\leqslant 2\beta$. Color-coding is a technique for dealing with such a situation where the subsets under consideration are small.

Let $Y$ be any subset of $X$ with $|Y|\leqslant k$. Let $X_{1},\ldots,X_{k^{2}}$ be a random partition of $X$. By standard balls and bins analysis, with probability at least $\frac{1}{4}$, $|Y\cap X_{i}|\leqslant 1$ for all $i\in[1,k^{2}]$, which implies that $\Sigma(Y)\in(X_{1}\cup\{0\})+\cdots+(X_{k^{2}}\cup\{0\})$. This probability can be boosted to $1-q$, if we repeat the above procedure for $\lceil\log_{4/3}q\rceil$ times and take the union of the resulting sumsets.

Bringmann [Bri17] proposed a two-layer color coding technique that reduces the number of subsets in the partition by roughly a factor of $k$. Let $q$ be the target error probability. The first layer of color coding randomly partitions $X$ into roughly $k/\log(k/q)$ subsets. With probability at least $1-q/2$, each subset contains at most $6\log(k/q)$ elements from $Y$. The second layer randomly partitions each of the subsets obtained in this first layer into $36\log^{2}(k/q)$ subsets. The second-layer partition will be repeated for $\lceil\log\frac{k}{q}\rceil$ times in order to boost the success probability to $1-q/2$. See Algorithm 1 for details.

By adjusting the error probability by a factor of $\frac{2\beta}{\varepsilon}$, we can have, with probability at least $1-q$, that $\bigcup_{j=1}^{r}S^{j}_{1}+\cdots+\bigcup_{j=1}^{r}S^{j}_{m}$ contains all the elements of ${\cal S}_{X}[\frac{\beta}{\varepsilon},\frac{2\beta}{\varepsilon}]$.

For technical reasons, we need an extra property that for any partition of $X$ obtained from coloring-coding, the sum of the maximum elements of the subsets is large. That is, we need, for all $j$,

where the maximum of an empty set is defined to be $0$. We claim that this property can be assured with a slight modification of the color coding algorithm. Details will be provided in Appendix B.

The proof of the lemma is deferred to Appendix B.

Throughout the rest of the paper, we fix $q^{*}:=(\frac{n}{\varepsilon})^{-O(1)}$, $m$ to be $4\beta/\log\frac{4\beta^{2}}{\varepsilon q^{*}}$ rounded up to next power of $2$, $g$ to be $36\log^{2}\frac{4\beta^{2}}{\varepsilon q^{*}}$ rounded up to next power of $2$, and $r:=\lceil\log\frac{4\beta^{2}}{\varepsilon q^{*}}\rceil$.

Let $\{X^{j}_{1,1},\ldots,X^{j}_{m,g}\}_{j\in[1,r]}$ be the $r$ partitions of $X$ obtained via Lemma 10. To simplify the notation, we assume that every subset in the $r$ partitions of $X$ is a set (rather than a multi-set), and that every subset contains $0$. This assumption is without loss of generality, because when we define $S^{j}_{i}$ in Lemma 10, we always add $0$ to the subsets of $X$ . To approximate ${\cal S}_{X}[\frac{\beta}{\varepsilon},\frac{2\beta}{\varepsilon}]$, it suffices to compute $S=\bigcup_{j=1}^{r}S^{j}_{1}+\cdots+\bigcup_{j=1}^{r}S^{j}_{m},$ where $S^{j}_{i}$ is defined in Lemma 10.

The procedure for computing $S$ can be viewed as a tree. The level $0$ of the tree has $mg$ leaves that represent the $mg$ subsets of $X$ in the $j$th partition. Given level $i$, we compute level $i+1$ by taking the sumset of every two nodes in level $i$. Therefore, in level $\log g$, we will obtain $S^{j}_{1},\ldots,S^{j}_{m}$. The computation from level $0$ to level $g$ will be repeated for $r$ times, so we can get $S^{j}_{1},\ldots,S^{j}_{m}$ for all $j$. Then we take union and get a new level $\log g$ consisting of $\cup_{j}S^{j}_{1},\ldots,\cup_{j}S^{j}_{m}$. Then we continue to compute level $1+\log g,2+\log g,\ldots$ until we get a single node (set) in level $\log mg$.

Given a level $h$, if we compute the sumset of two sets via standard FFT (Lemma 4), it would require $O(\frac{mg}{2^{h}}\cdot\frac{2^{h}}{\varepsilon}\log\frac{2^{h}}{\varepsilon})=\widetilde{O}(\frac{\beta}{\varepsilon})$ time to obtain the next level. This is already too much as $\beta$ can be as large as $\frac{1}{\varepsilon}$.

Our algorithm computes a new level only if the nodes in this level have a total size of roughly $\widetilde{O}(\frac{1}{\varepsilon})$. We say a level is sparse in this case. A sparse level can computed in nearly $\widetilde{O}(\frac{1}{\varepsilon})$ via the output-sensitive algorithm for sumset whose running time is linear in the output size (Lemma 5). The only exception is level $0$: in $O(n)$ time, we can determine whether it is sparse or not, and we will try to compute level 1 only if level $0$ is sparse. Recall that there are $1+\log mg$ levels and that the first $1+\log g$ levels may be repeated but only for $r$ times. Both $1+\log mg$ and $r$ are logarithmic in $n$, $\frac{1}{\varepsilon}$ and $\beta$. So the total running time for computing $S$ will be $\widetilde{O}(n+\frac{1}{\varepsilon})$, if all levels are sparse. For dense levels, we cannot afford to compute them. Instead, we use additive combinatorics tools to show that if some level is dense, ${\cal S}_{X}$ must have a long sequence with a small difference between consecutive terms. Then ${\cal S}_{X}[\frac{\beta}{\varepsilon},\frac{2\beta}{\varepsilon}]$ can be immediately approximated via the following lemma.

We formalize the concepts of “dense” and “sparse” and derive some properties resulting from them. The core of our technique is an additive combinatorics result from Szemerédi and Vu [SV05], which basically states that given many large-sized sets of integers, their sumset must have a long arithmetic progression.

Throughout the rest of the paper, $c$ denotes the constant in the above corollary.

An arithmetic progression of length $u$ is not long enough for our purpose. To produce a longer sequence, we need a collection of integer sets to be $\gamma$-dense.

Through the next two lemmas, we will prove that, when a collection is $\gamma$-dense, we can use it to produce a long sequence with a small difference between consecutive elements. Basically, we use a small fraction of the collection to produce an arithmetic progression of length $u$, and use the rest of the collection to extend this progression to a longer sequence. We first show how to extend an arithmetic progression.

Now we are ready to prove that if $A_{1},\ldots,A_{\ell}$ is $\gamma$-dense, their sumset must contain a long sequence with small differences between consecutive terms.