Approximating Subset Sum Ratio via Subset Sum Computations

Abstract

We present a new FPTAS for the Subset Sum Ratio problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for the closely related Subset Sum problem, hence any progress over those—such as the recent improvement due to Bringmann and Nakos [SODA 2021]—carries over to our FPTAS. Depending on the relationship between the size of the input set n and the error margin $\varepsilon$, we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity $\mathcal {O} (n^4 / \varepsilon )$. In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the Subset Sum algorithm used. Furthermore, while the aforementioned state of the art complexity, expressed in the form $\mathcal {O} ((n + 1 / \varepsilon )^c)$, has constant $c = 5$, our results establish that $c < 5$.

Aris Pagourtzis and Stavros Petsalakis were supported in part by the PEVE 2020 basic research support program of the National Technical University of Athens.

1 Introduction

One of Karp’s 21 NP-complete problems [18], Subset Sum has seen astounding progress over the last few years. Koiliaris and Xu [21], Bringmann [7] and Jin and Wu [17] have presented pseudopolynomial algorithms resulting in substantial improvements over the long-standing standard approach of Bellman [6], and the improvement by Pisinger [29]. Moreover, the latter two algorithms [7, 17] match the SETH-based lower bounds proved in [1]. Additionally, recently there has been progress in the approximation scheme of Subset Sum, the first such improvement in over 20 years, with a new algorithm introduced by Bringmann and Nakos [9], as well as corresponding lower bounds obtained through the lens of fine-grained complexity.

The Equal Subset Sum problem, which, given an input set, asks for two disjoint subsets of equal sum, is closely related to Subset Sum. It finds applications in multiple different fields, ranging from computational biology [10, 13] and computational social choice [22], to cryptography [30], to name a few. In addition, it is related to important theoretical concepts such as the complexity of search problems in the class TFNP [28].

The centerpiece of this paper is the Subset Sum Ratio problem, the optimization version of Equal Subset Sum, which asks, given an input set $S \subseteq \mathbb {N}$, for two disjoint subsets $S_1, S_2 \subseteq S$, such that the following ratio is minimized

We present a new approximation scheme for this problem, highlighting its close relationship with the classical Subset Sum problem. Our proposed algorithm is the first to associate these closely related problems and, depending on the relationship of the cardinality of the input set n and the value of the error margin $\varepsilon$, achieves better asymptotic bounds than the current state of the art [23]. Moreover, while the complexity of the current state of the art approximation scheme expressed in the form $\mathcal{O}( ( n + 1 / \varepsilon )^c )$ has an exponent $c = 5$, we present an FPTAS with constant $c < 5$.

1.1 Related Work

Equal Subset Sum as well as its optimization version called Subset Sum Ratio [5] are closely related to problems appearing in many scientific areas. Some examples include the Partial Digest problem, which comes from computational biology [10, 13], the allocation of individual goods [22], tournament construction [20], and a variation of Subset Sum, called Multiple Integrated Sets SSP, which finds applications in the field of cryptography [30]. Furthermore, it is related to important concepts in theoretical computer science; for example, a restricted version of Equal Subset Sum lies in a subclass of the complexity class $\mathsf {TFNP}$, namely in $\mathsf {PPP}$ [28], a class consisting of search problems that always have a solution due to some pigeonhole argument, and no polynomial time algorithm is known for this restricted version.

Equal Subset Sum has been proven NP-hard by Woeginger and Yu [31] (see also the full version of [25] for an alternative proof) and several variations have been proven NP-hard by Cieliebak et al. in [11, 12]. A 1.324-approximation algorithm has been proposed for Subset Sum Ratio in [31] and several FPTASs appeared in [5, 23, 27], the fastest so far being the one in [23] of complexity $\mathcal{O}(n^4/\varepsilon )$, the complexity of which seems to also apply to various meaningful special cases, as shown in [24].

As far as exact algorithms are concerned, recent progress has shown that Equal Subset Sum can be solved probabilistically in¹ $\mathcal{O}^{*}(1.7088^n)$ time [25], faster than a standard “meet-in-the-middle” approach yielding an $\mathcal{O}^{*}(3^{n/2}) \le \mathcal{O}^{*}(1.7321^n)$ time algorithm.

These problems are tightly connected to Subset Sum, which has seen impressive advances recently, due to Koiliaris and Xu [21] who gave a deterministic $\tilde{\mathcal{O}}(\sqrt{n}t)$ algorithm, where n is the number of input elements and t is the target, and by Bringmann [7] who gave a $\tilde{\mathcal{O}}(n + t)$ randomized algorithm, which is essentially optimal under SETH [1]. See also [2] for an extension of these algorithms to a more general setting. Jin and Wu subsequently proposed a simpler randomized algorithm [17] achieving the same bounds as [7], which however seems to only solve the decision version of the problem. Recently, Bringmann and Nakos [8] have presented an algorithm, where $\mathcal {S}_t(Z)$ is the set of all subset sums of the input set Z that are smaller than t, based on top-k convolution.

Regarding approximation schemes for Subset Sum, recently Bringmann and Nakos [9] presented the first improvement in over 20 years, since the scheme of [19] had remained the state of the art. Making use of modern techniques, they additionally provide lower bounds based on the popular min-plus convolution conjecture [14]. Furthermore, they present a new FPTAS for the closely related Partition problem, by observing that their techniques can be used to approximate a slightly more relaxed version of the Subset Sum problem, firstly studied in [25].

1.2 Our Contribution

We present a novel approximation scheme for the Subset Sum Ratio problem. Our algorithm makes use of exact and approximation algorithms for Subset Sum, thus, any improvement over those carries over to our proposed scheme. Additionally, depending on the relationship between n and $\varepsilon$, our algorithm improves upon the best existing approximation scheme of [23].

We start by presenting some necessary background in Sect. 2. Afterwards, in Sect. 3 we introduce an FPTAS for a restricted version of the problem. In the following Sect. 4, we explain how to make use of the algorithm presented in the previous section, in order to obtain an approximation scheme for the Subset Sum Ratio problem. The complexity of the final scheme is thoroughly analyzed in Sect. 5, followed by some possible directions for future research in Sect. 6.

2 Preliminaries

Let, for $x \in \mathbb {N}$, $[x] = \{ 0, \ldots , x \}$ denote the set of integers in the interval [0, x]. Given a set $S \subseteq \mathbb {N}$, denote its largest element by $\max (S)$ and the sum of its elements by $\varSigma (S) = \sum _{s \in S} s$. If we are additionally given a value $\varepsilon \in (0, 1)$, define the following partition of its elements:

• The set of its large elements as . Note that $\max (S) \in L(S, \varepsilon )$, for any $\varepsilon \in (0, 1)$.

• The set of its small elements as .

In the following, since the values of the associated parameters will be clear from the context, they will be omitted and we will refer to these sets simply as L and M.

The following definitions will be useful for the rest of this paper.

Definition 1

(Closest Set and pair). Given a set $S_i \subseteq A$, we define as its closest set a set $S_{i, \mathrm {opt}}$ such that $S_{i, \mathrm {opt}} \subseteq A \backslash S_i$ and ${\varSigma (S_i) \ge \varSigma (S_{i, \mathrm {opt}})} \ge {\varSigma (S')}$ for all $S' \subseteq A \backslash S_i$. The pair $(S_i,S_{i, \mathrm {opt}})$ is called closest pair.

Definition 2

($\varepsilon$-close set and pair). Given a set $S_i \subseteq A$, we define as its $\varepsilon$-close set a set $S_{i, \varepsilon }$ such that $S_{i, \varepsilon } \subseteq A \backslash S_i$ and $\varSigma (S_i) \ge \varSigma (S_{i, \varepsilon }) \ge (1-\varepsilon ) \cdot \varSigma (S_{i, \mathrm {opt}})$. The pair $(S_i,S_{i, \varepsilon })$ is called $\varepsilon$-close pair.

Remark 1

Note that $S_{i, \mathrm {opt}}$ is also an $\varepsilon$-close set of $S_i$ for any $\varepsilon \in (0,1)$.

Definition 3

(Subset Sum). Given a set X and target t, compute a subset $Y \subseteq X$, such that .

Definition 4

(Approximate Subset Sum). Given a set X, target t and error margin $\varepsilon$, compute a subset $Y \subseteq X$ such that $(1 - \varepsilon ) \cdot OPT \le \varSigma (Y) \le OPT$, where .

By solving Subset Sum or its approximate version, one can compute an $\varepsilon$-close set for a given subset $S_i \subseteq A$ as follows.

• 1. Closest set ($S_{i, \mathrm {opt}}$) computation Compute the subset sums of set $A \backslash S_i$ with target $\varSigma (S_i)$ and keep the largest non exceeding. This can be achieved by a standard meet in the middle [16] algorithm.

• 2. $\varepsilon$-close set ($S_{i, \varepsilon }$) computation Run an approximate Subset Sum algorithm [9, 19] with error margin $\varepsilon$ on set $A \backslash S_i$ with target $\varSigma (S_i)$.

3 Approximation Scheme for a Restricted Version

In this section, we present an FPTAS for the constrained version of the Subset Sum Ratio problem where we are only interested in approximating solutions that involve large subset sums. By this, we mean that for at least one of the subsets of the optimal solution, the sum of its large elements must be no less than $\max (A) = a_n$ (assuming that $A = \{ a_1, \ldots , a_n \}$ is the sorted input set); let $r_{\mathrm {opt}}$ denote the subset sum ratio of such an optimal solution. Our FPTAS will return a solution of ratio r, such that $1 \le r \le (1 + \varepsilon ) \cdot r_{\mathrm {opt}}$, for a given error margin $\varepsilon \in (0, 1)$; however, we allow that the sets of the returned solution do not necessarily satisfy the aforementioned constraint (i.e. the sum of their large elements may be less than $a_n$).

3.1 Outline of the Algorithm

We now present a rough outline of the algorithm, along with its respective pseudocode:

• At first, we search for approximate solutions involving exclusively large elements from $L(A,\varepsilon )$.

• To this end, we produce the subset sums formed by these large elements. If their number exceeds $n / \varepsilon ^2$, then we can easily find an approximate solution.

• Otherwise, for each of the produced subsets, we find its corresponding $\varepsilon '$-close set, for some appropriate $\varepsilon '$ defined later.

• Then, it suffices to consider only these pairs of subsets when searching for an approximate solution.

• In the case that the optimal solution involves small elements, we can approximate it by adding elements of $M(A, \varepsilon )$ in a greedy way.

3.2 Regarding only Large Elements

We firstly search for an $(1 + \varepsilon )$-approximate solution with $\varepsilon \in (0,1)$, without involving any of the elements that are smaller than $\varepsilon \cdot a_n$. Let be the set of small elements and be the set of large elements.

After partitioning the input set, we split the interval $[0, n \cdot a_n]$ into smaller intervals, called bins, of size $l = \varepsilon ^2 \cdot a_n$ each, as depicted in Fig. 1.

Fig. 1.

Split of the interval $[ 0, n \cdot a_n ]$ to bins of size l.

Thus, there are a total of $B = n / \varepsilon ^2$ bins. Notice that each possible subset of the input set will belong to a respective bin constructed this way, depending on its sum. Additionally, if two sets correspond to the same bin, then the difference of their subset sums will be at most l.

The next step of our algorithm is to generate all the possible subset sums, occurring from the set of large elements L. The complexity of this procedure is , where |L| is the cardinality of set L. Notice however, that it is possible to bound the number of the produced subset sums by the number of bins B, since if two sums belong to the same bin they constitute a solution, as shown in Lemma 1, in which case the algorithm terminates in time $\mathcal{O}(n / \varepsilon ^2)$.

Lemma 1

If two subsets correspond to the same bin, we can find an $(1 + \varepsilon )$-approximation solution.

Proof

Suppose there exist two sets $L_1, L_2 \subseteq L$ whose sums correspond to the same bin, with $\varSigma (L_1) \le \varSigma (L_2)$. Notice that there is no guarantee regarding the disjointness of said subsets, thus consider $L'_1 = L_1 \backslash L_2$ and $L'_2 = L_2 \backslash L_1$, for which it is obvious that $\varSigma (L_1') \le \varSigma (L_2')$.

Additionally, assume that $L'_1 \ne \emptyset$. Then it holds that

$$ \varSigma (L_2') - \varSigma (L_1') = \varSigma (L_2) - \varSigma (L_1) \le l $$

Therefore, the sets $L'_1$ and $L'_2$ constitute an $(1+\varepsilon )$-approximation solution, since

$$\begin{aligned} \frac{\varSigma (L_2')}{\varSigma (L_1')}&\le \frac{\varSigma (L_1') + l}{\varSigma (L_1')} = 1 + \frac{l}{\varSigma (L_1')}\\&\le 1 + \frac{\varepsilon ^2 \cdot a_n}{\varepsilon \cdot a_n} = 1 + \varepsilon \end{aligned}$$

where the last inequality is due to the fact that $L_1' \subseteq L$ is composed of elements $\ge \varepsilon \cdot a_n$, thus $\varSigma (L_1') \ge \varepsilon \cdot a_n$.

It remains to show that $L'_1 \ne \emptyset$. Assume that $L'_1 = \emptyset$. This implies that $L_1 \subseteq L_2$ and since we consider each subset of L only once and the input is a set and not a multiset, it holds that $L_1 \subset L_2 \implies L'_2 \ne \emptyset$. Since $L_1$ and $L_2$ correspond to the same bin, it holds that

$$ \varSigma (L_2) - \varSigma (L_1) \le l \implies \varSigma (L_2') - \varSigma (L_1') \le l \implies \varSigma (L'_2) \le l $$

which is a contradiction, since $L'_2$ is a non empty subset of L, which is comprised of elements greater than or equal to $\varepsilon \cdot a_n$, hence $\varSigma (L'_2) \ge \varepsilon \cdot a_n > \varepsilon ^2 \cdot a_n = l$, since $\varepsilon < 1$.

Consider an $\varepsilon '$ such that $1/(1-\varepsilon ') \le 1 + \varepsilon$ for all $\varepsilon \in (0, 1)$, for instance $\varepsilon ' = \varepsilon /2$ (the exact value of $\varepsilon '$ will be computed in Sect. 5). If every produced subset sum of the previous step belongs to a distinct bin, then, we compute their respective $\varepsilon '$-close sets, as described in Sect. 2. We can approximate an optimal solution that involves exclusively large elements using these pairs.

Before we prove the previous statement, observe that, if the optimal solution involves sets $L_1, L_2 \subseteq L$ composed only of large elements, where $\varSigma (L_1) \le \varSigma (L_2)$, then $\varSigma (L_1) = \varSigma (L_{2, \mathrm {opt}})$, where $L_{2, \mathrm {opt}}$ is a closest set of $L_2$, with respect to the set $L \backslash L_2$.

Lemma 2

If the optimal ratio $r_{\mathrm {opt}}$ involves sets consisting of only large elements, then there exists an $\varepsilon '$-close pair with ratio $r \le (1 + \varepsilon ) \cdot r_{\mathrm {opt}}$.

Proof

Assume that the sets $S^*_1, S^*_2 \subseteq L$ form the optimal solution $(S^*_2,S^*_1)$ and $\frac{\varSigma (S^*_2)}{\varSigma (S^*_1)} = r_{\mathrm {opt}} \ge 1$ is the optimal ratio. Then, as mentioned, it holds that $\varSigma (S^*_1) = \varSigma (S^*_{2, \mathrm {opt}})$. For each set of large elements, there exists an $\varepsilon '$-close set and a corresponding $\varepsilon '$-close pair; let $(S^*_2, S^*_{2, \varepsilon '})$ be this pair for set $S^*_2$. Then,

$$ \varSigma (S^*_2) \ge \varSigma (S^*_1) = \varSigma (S^*_{2, \mathrm {opt}}) \ge \varSigma (S^*_{2, \varepsilon '}) \ge (1 - \varepsilon ') \cdot \varSigma (S^*_1) $$

Thus, it holds that

$$ 1 \le \frac{\varSigma (S^*_2)}{\varSigma (S^*_{2, \varepsilon '})} \le \frac{1}{(1 - \varepsilon ')} \cdot \frac{\varSigma (S^*_2)}{\varSigma (S^*_1)} \le (1 + \varepsilon ) \cdot r_{\mathrm {opt}} $$

Therefore, we have proved that in the case where the optimal solution consists of sets comprised of only large elements, it is possible to find an ($1 + \varepsilon$)-approximation solution. This is achieved by computing an $\varepsilon '$-close set for each subset $L_i \subseteq L$ belonging in some bin, using the algorithms described in the preliminaries, with respect to set $L \backslash L_i$ and target $\varSigma (L_i)$. The total cost of these algorithms will be thoroughly analyzed in Sect. 5 and depends on the algorithm used.

It is important to note that by utilizing an (exact or approximation) algorithm for Subset Sum, we establish a connection between the complexities of Subset Sum and approximating Subset Sum Ratio in a way that any future improvement in the first carries over to the second.

3.3 General $(1+\varepsilon )$-Approximation Solutions

Whereas we previously considered optimal solutions involving exclusively large elements, here we will search for approximations for those optimal solutions that use all the elements of the input set, hence include small elements, and satisfy our constraint. We will prove that in order to approximate those optimal solutions, it suffices to consider only the $\varepsilon '$-close pairs corresponding to each distinct bin and add small elements to them. In other words, instead of considering any two random disjoint subsets consisting of large elements² and subsequently adding to these the small elements, we can instead consider only the pairs computed in the previous step, the number of which is bounded by the number of bins $B = n / \varepsilon ^2$. Moreover, we will prove that it suffices to add the small elements to our solution in a greedy way.

Since the algorithm has not detected a solution so far, due to Lemma 1 every computed subset sum of set L belongs to a different bin. Thus, their total number is bounded by the number of bins B, i.e.

We proceed by involving small elements in order to reduce the difference between the sums of $\varepsilon '$-close pairs, thus reducing their ratio.

Lemma 3

Given the $\varepsilon '$-close pairs, one can find an $(1 + \varepsilon )$-approximation solution for the constrained version of Subset Sum Ratio, in the case that the optimal solution involves small elements.

Proof

(sketch). Due to page limitations, we only give a short sketch of the proof here; the complete proof is included in the full version of the paper.

Let $S^*_1 = L^*_{1} \cup M^*_{1}$ and $S^*_2 = L^*_{2} \cup M^*_{2}$ be disjoint subsets that form an optimal solution, where $\varSigma (S^*_1) \le \varSigma (S^*_2)$, $L^*_{1}, L^*_{2} \subseteq L$ and $M^*_{1}, M^*_{2} \subseteq M$.

For $\varSigma (L^*_1) < \varSigma (L^*_2)$ (respectively $\varSigma (L^*_2) < \varSigma (L^*_1)$), we show that is suffices to add an appropriate subset $M_k \subseteq M$ to $L^*_{2,\varepsilon '}$ (respectively $L^*_{1,\varepsilon '}$) in order to approximate the optimal solution $r_{\mathrm {opt}} = \frac{\varSigma (S^*_2)}{\varSigma (S^*_1)}$, where and $k \le |M|$.

Therefore, by adding in a greedy way small elements to an $\varepsilon '$-close set of the set with the largest sum among $L^*_1$ and $L^*_2$, we can successfully approximate the optimal solution.

Adding Small Elements Efficiently. Here, we will describe a method to efficiently add small elements to our sets. As a reminder, up to this point the algorithm has detected an $\varepsilon '$-close pair $(L_2, L_1)$, such that $L_1, L_2 \subseteq L$ with $\varSigma (L_1) < \varSigma (L_2)$. Thus, we search for some k such that $\varSigma (L_1 \cup M_k) \le \varSigma (L_2) + \varepsilon \cdot a_n$, where . Notice that if $\varSigma (M) \ge \varSigma (L_2) - \varSigma (L_1)$, there always exists such a set $M_k$, since by definition, each element of set M is smaller than $\varepsilon \cdot a_n$. In order to determine $M_k$, we make use of an array of partial sums $T[k] = \varSigma (M_k)$, where $k \le |M|$. Notice that T is sorted; therefore, since T is already available (see Algorithm 2), each time we need to compute a subset with the desired property, this can be done in $\mathcal{O}(\log k) = \mathcal{O}(\log n)$ time.

4 Final Algorithm

The algorithm presented in the previous section constitutes an approximation scheme for Subset Sum Ratio, in the case where at least one of the solution subsets has sum of its large elements greater than, or equal to the max element of the input set. Thus, in order to solve the Subset Sum Ratio problem, it suffices to run the previous algorithm n times, where n depicts the cardinality of the input set A, while each time removing the max element of A.

In particular, suppose that the optimal solution involves disjoint sets $S_1^*$ and $S_2^*$, where $a_k = \max \{ S_1^* \cup S_2^* \}$. There exists an iteration for which the algorithm considers as input the set $A_k = \{ a_1, \ldots , a_k \}$. In this iteration, the element $a_k$ is the largest element and the algorithm searches for a solution where the sum of the large elements of one of the two subsets is at least $a_k$. The optimal solution has this property so the ratio of the approximate solution that the algorithm of the previous section returns is at most $(1 + \varepsilon )$ times the optimal.

Consequently, n repetitions of the algorithm suffice to construct an FPTAS for Subset Sum Ratio.

Notice that if at some repetition, the sets returned due to the algorithm of Sect. 3 have ratio at most $1 + \varepsilon$, then this ratio successfully approximates the optimal ratio $r_{\mathrm {opt}} \ge 1$, since $1 + \varepsilon \le (1 + \varepsilon ) \cdot r_{\mathrm {opt}}$, therefore they constitute an approximation solution.

5 Complexity

The total complexity of the final algorithm is determined by three distinct operations, over the n iterations of the algorithm:

• 1. The cost to compute all the possible subset sums occurring from large elements. It suffices to consider the case where this is bounded by the number of bins $B = n / \varepsilon ^2$, due to Lemma 1.

• 2. The cost to find the $\varepsilon '$-close pair for each subset in a distinct bin. The cost of this operation will be analyzed in the following subsection.

• 3. The cost to include small elements to the $\varepsilon '$-close pairs. There are B $\varepsilon '$-close pairs, and each requires $\mathcal{O}(\log n)$ time, thus the total time required is .

5.1 Complexity to Find the $\varepsilon '$-Close Pairs

Using Exact Subset Sum Computations. The first algorithm we mentioned is a standard meet in the middle algorithm. Here we will analyze its complexity.

Let subset $L' \subseteq L$ such that $|L'| = k$. The meet in the middle algorithm on the set $L \backslash L'$ costs time

$$ \mathcal{O}\left( \frac{|L \backslash L'|}{2} \cdot 2^{\frac{|L \backslash L'|}{2}} \right) . $$

Notice that the number of subsets of L of cardinality k is $\left( {\begin{array}{c}|L|\\ k\end{array}}\right)$ and that $|L| \le \log (n / \varepsilon ^2)$. Additionally,

$$\begin{aligned} \sum _{k = 0}^{|L|} \left( {\begin{array}{c}|L|\\ k\end{array}}\right) \cdot 2^{\frac{|L| - k}{2}} \cdot \frac{|L| - k}{2}&= 2^{|L|/2} \cdot \sum _{k = 0}^{|L|} \left( {\begin{array}{c}|L|\\ k\end{array}}\right) \cdot 2^{-k / 2} \cdot \frac{|L| - k}{2}\\&\le 2^{|L|/2} \cdot \frac{|L|}{2} \cdot \sum _{k = 0}^{|L|} \left( {\begin{array}{c}|L|\\ k\end{array}}\right) \cdot 2^{-k / 2} \end{aligned}$$

Furthermore, let $c = (1 + 2^{-1/2})$, where $\log c = 0.7715... < 0.8$. Due to Binomial Theorem, it holds that

$$\begin{aligned} \sum _{k = 0}^{|L|} \left( {\begin{array}{c}|L|\\ k\end{array}}\right) \cdot 2^{-k / 2} = (1 + 2^{-1/2})^{|L|} = c^{|L|} \le c^{\log (n / \varepsilon ^2)} = (n / \varepsilon ^2) ^ {\log c} \end{aligned}$$

Consequently, the complexity to find a closest set for every subset in a bin is

Using approximate Subset Sum computations. Here we will analyze the complexity in the case we run an approximate Subset Sum algorithm in order to compute the $\varepsilon '$-close pairs.

For subset $L_i \subseteq L$ of sum $\varSigma (L_i)$, we run an approximate Subset Sum algorithm ([9, 19]), with error margin $\varepsilon '$ such that

$$ \frac{1}{1-\varepsilon '} \le 1 + \varepsilon \iff \varepsilon ' \le \frac{\varepsilon }{1 + \varepsilon } $$

By choosing the maximum such $\varepsilon '$, we have that

Thus, if we use for instance the approximation algorithm³ presented at [19], the complexity of finding all the $\varepsilon '$-close sets (one for every subset in a bin, for a total of a maximum of $B = n / \varepsilon ^2$ subsets) is

5.2 Total Complexity

The total complexity of the algorithm occurs from the n distinct iterations required and depends on the algorithm chosen to find the $\varepsilon '$-close pairs, since both of the presented algorithms dominate the time of the rest of the operations. Thus, by choosing the fastest one (depending on the relationship between n and $\varepsilon$), the final complexity is

6 Conclusion and Future Work

The main contribution of this paper, apart from the introduction of a new FPTAS for the Subset Sum Ratio problem, is the establishment of a connection between Subset Sum and approximating Subset Sum Ratio. In particular, we showed that any improvement over the classic meet in the middle algorithm [16] for Subset Sum, or over the approximation scheme for Subset Sum will result in an improved FPTAS for Subset Sum Ratio.

Additionally, we establish that the complexity of approximating Subset Sum Ratio, expressed in the form $\mathcal{O}( ( n + 1 / \varepsilon )^c )$ has an exponent $c < 5$, which is an improvement over all the previously presented FPTASs for the problem.

It is important to note however, that there is a distinct limit to the complexity that one may achieve for the Subset Sum Ratio problem using the techniques discussed in this paper.

As a direction for future research, we consider the notion of the weak approximation of Subset Sum, as discussed in [9, 26], which was used in order to approximate the slightly easier Partition problem, and may be able to replace the approximate Subset Sum algorithm in the computation of the $\varepsilon '$-close sets.

Another possible direction could be the use of exact Subset Sum algorithms parameterized by a concentration parameter $\beta$, as described in [3, 4], where they solve the decision version of Subset Sum. See also [15] for a use of this parameter under a pseudopolynomial setting. It would be interesting to investigate whether analogous arguments could be used to solve the optimization version.