Approximation Schemes for k-Subset Sum Ratio and k-Way Number Partitioning Ratio

Let $S=(S_1,\mathrm{\dots },S_k)$ be an arbitrary feasible solution. If it violates property 1, i.e. there exists a set $S_i$ in $S$ that only contains elements $j$ with $a_j\le Q$ and has sum $\mathrm{\Sigma }(S_i,A)\ge 2Q$, we transform it as follows. For all $j\in S_i$, we have

Thus, if we remove an element $j$ from $S_i$, the ratio cannot increase. We remove the smallest element from $S_i$. As long as the solution still has a set $S_i$ violating property 1, we can apply the same process repeatedly, until there are no more such sets. Since we are only removing elements, no new sets violating property 1 may appear during this process. Note that the largest element of every set remains intact, therefore the $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ restrictions $max(S_1)=p$ and $\max (S_i)>p$ for are satisfied.

If the new solution $S^{\prime }$ violates property 2, i.e. it contains a set $S_i$ with an element $j$ s.t. $a_j>Q$ and $|S_i|>1$, we apply the following transformation. It holds that

As such, replacing set $S_i$ with set $\{j\}$ will result in equal or smaller ratio. We repeat this for every such set $S_i$, thus yielding a solution in which every such set is a singleton. Note that the derived solution is a feasible $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ solution and it still satisfies property 1, since we did not modify sets that contain only elements $j$ with $a_j\le Q$.

Finally, if the new solution $S^{\prime \prime }$ violates property 3, i.e. it contains a singleton set $\{u\}$ s.t. $a_u>Q$ and there is an unselected⁷⁷7An element that is not in any set $S_i$ of the solution. element $v$ such that , we do the following. It holds that

Thus, selecting $v$ instead of $u$ does not increase the ratio. Repeating this for all $u$ and $v$ satisfying the above mentioned property forces the union of these singleton sets to contain the smallest indices possible, yielding a feasible solution that satisfies all three properties.

In conclusion, for any feasible solution we can find another one that satisfies all properties 1, 2, 3 and has equal or smaller ratio. Thus, applying this to an arbitrary optimal solution proves the theorem. $◀$

Let $S$ be a $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ solution. Split $S$ in two: $S_{small}$, containing the $k^{\prime }$ sets returned by Algorithm 2, and $S_{large}$, containing the singletons $\{j\}$ s.t. $a_j>Q$. Assume $S_{small}$ uses $C_1$.

By assumption, $C_1$ and $C_2$ have identical $D$ and $V$ vectors and their sets involve only elements from $[i]$. This implies that any combination of elements larger than $i$ that can later be added to sets of $C_1$ to construct a partial⁹⁹9We denote as partial a solution for which $S_{large}$ will be appended to obtain a feasible $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ solution. solution with vectors $D^{\prime },V^{\prime }$ can also be added to the corresponding sets of $C_2$ to construct a partial solution with the same vectors $D^{\prime },V^{\prime }$. Let $S_{small}^{\prime }$ be the partial solution obtained by using $C_2$ instead of $C_1$ and adding the same combination of elements that would have been used to obtain $S_{small}$ from $C_1$. Consider the solution $S^{\prime }$ that is obtained by appending $S_{large}$ to $S_{small}^{\prime }$. Note that $S_{small}$ and $S_{small}^{\prime }$ have the same validity vector, hence $S^{\prime }$ is also a feasible $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ solution.

Let $M_s,m_s$ be the maximum and minimum sum of $S_{small}$ respectively and $M_s^{\prime },m_s^{\prime }$ those of $S_{small}^{\prime }$. Since and the difference vector $D$ is the same for both solutions, it follows that , and $M_s-m_s=M_s^{\prime }-m_s^{\prime }$. From these, we obtain

Let $\{t\}\in S_{large}$ be the singleton set with the largest element. For all $\{i\}\in S_{large}$ such that $i\ne t$, we have

This implies that $\{i\}$ ($i\ne t$) does not affect the ratio and $\{t\}$ only affects the ratio if $a_t>M_s$. Thus, all the sets in $S_{large}$ can be ignored when calculating $ℛ(S,A)$, except for $\{t\}$ if $a_t>M_s$. The same holds for $ℛ(S^{\prime },A)$ and $M_s^{\prime }$. Consider three cases:

1. 1.

   . In this case, $ℛ(S,A)=a_t/m_s$ and $ℛ(S^{\prime },A)=a_t/m_s^{\prime }$. Since : $ℛ(S,A)>ℛ(S^{\prime },A)$.

2. 2.

   . In this case, $ℛ(S,A)=a_t/m_s>M_s/m_s$ and $ℛ(S^{\prime },A)=M_s^{\prime }/m_s^{\prime }$. By inequality (1): $ℛ(S,A)>ℛ(S^{\prime },A)$.

3. 3.

   . In this case, $ℛ(S,A)=M_s/m_s$ and $ℛ(S^{\prime },A)=M_s^{\prime }/m_s^{\prime }$. By inequality (1): $ℛ(S,A)>ℛ(S^{\prime },A)$.

In all cases $ℛ(S,A)>ℛ(S^{\prime },A)$, therefore $S$ cannot be optimal. $◀$

The $x$ singletons constructed by Algorithm 1 are disjoint and contain elements larger than $q$. In Algorithm 2, every element $i\le q$ is processed in increasing order and added to at most one set at a time. As such, all sets are disjoint. Note that $p$ is contained in $S_1$ and $S_1$ cannot receive a larger element. Recall that $v_i$ is set to true when $S_i$ receives an element $j>p$ and Algorithm 2 only returns solutions with $V=[\text{true},\mathrm{\dots },\text{true}]$. Thus, all $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ restrictions regarding the largest element of each set are satisfied. $◀$

The proof of the following theorem uses Lemmas 10 and 11. The main idea is to show that Algorithm 1 considers and therefore finds the optimal solution whose existence is guaranteed by Theorem 9.

Lemma 11 guarantees that Algorithm 1 returns a feasible $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ solution, so we only need to prove that its ratio is optimal. Let $S^{\ast }$ be the optimal $k\text{-}{\mathrm{SSR}}_{\mathrm{R}}$ solution guaranteed by Theorem 9. We split $S^{\ast }$ in two: $S_{large}^{\ast }$, which contains the singleton sets $\{j\}$ s.t. $a_j>Q$, and $S_{small}^{\ast }$, which contains the rest of the sets. Note that the number $x$ of these singletons is bounded by $k-1$ or by the amount of sufficiently large elements, i.e. $n-q$. Thus, Algorithm 1 considers every $S_{large}$ that satisfies properties 2 and 3 of Theorem 9, including $S_{large}^{\ast }$.

Recall that Algorithm 1 uses Algorithm 2 as a subroutine in order to obtain candidate partial solutions, to which $S_{large}^{\ast }$ will be appended. We would like $S_{small}^{\ast }$ to be contained in the solutions returned by Algorithm 2.

Algorithm 2 prunes a solution if a difference $d_j$ would become lower than or equal to $-2Q$. Any $S_{small}$ satisfying property 1 of Theorem 9 will not be affected by this. This includes $S_{small}^{\ast }$.

When there is a conflict in a cell $T_i[D][V]$ between two tuples with different $su{m}_1$ values, $S_{small}^{\ast }$ cannot use the one with smaller $su{m}_1$ (by Lemma 10), since $S^{\ast }$ is a optimal. When there is a conflict in a cell $T_i[D][V]$ between two tuples $C_1,C_2$ with equal $su{m}_1$ values, observe that both tuples have exactly the same sums (but different sets), use only elements up to $i$ and have the same validity vector. This implies that any combination of elements greater than $i$ that can later be added to sets of $C_1$ can also be added to the same sets of $C_2$ and vice versa. Thus, any combination of sums that can be reached through $C_1$ can also be reached through $C_2$ and vice versa. This means that if one of these tuples leads to $S_{small}^{\ast }$, the other one leads to another partial solution $S_{small}^{\ast \ast }$, which has exactly the same sums as $S_{small}^{\ast }$. Appending $S_{large}^{\ast }$ to $S_{small}^{\ast \ast }$ yields a solution with the same sums as $S^{\ast }$, i.e. another optimal solution.

It follows directly from the description of Algorithm 2 that it constructs every possible combination of disjoint sets $S_1,\mathrm{\dots },S_{k-x}$ with $\max (S_1)=p$, apart from the ones pruned as explained in the previous paragraphs.

Therefore, the partial solutions returned by Algorithm 2 contain $S_{small}^{\ast }$ or another partial solution with the same sums, which also leads to an optimal solution when appended with $S_{large}^{\ast }$. In either case, Algorithm 1 will find an optimal solution when iterating to find the best ratio. $◀$

Algorithm 1 calls Algorithm 2 once for each value of $x$ in $\{0,\mathrm{\dots },\min \{k-1,n-q\}\}$, where $x$ is the number of singleton sets $\{j\}$ s.t. $a_j>Q$. For a fixed $x$, Algorithm 2 is applied to an instance with $k^{\prime }=k-x$ sets and $q=O(n)$ elements.

Due to the pruning done in Algorithm 2, it holds that $\forall j\in \{2,\mathrm{\dots },k^{\prime }\}$: , where the second inequality holds because $\mathrm{\Sigma }(S_1,A)\le Q$. Since the algorithm stores $D$ in non-decreasing order (i.e., $d_2\le d_3\le \mathrm{\cdots }\le d_{k^{\prime }}$), there are $O({(3Q)}^{k^{\prime }-1}/(k^{\prime }-1)!)$ distinct difference vectors. Taking into account the validity vector $V$ and all $T_i$’s, we obtain the following bound for the amount of DP cells: $O(n{(6Q)}^{k^{\prime }-1}/(k^{\prime }-1)!)$.

For constant $k$, this bound becomes $O(n{Q}^{k^{\prime }-1})$. Note that all operations of Algorithm 2 on DP cells (such as sorting the difference vector after adding an element) run in time $O(k^{\prime })$, so the time complexity of Algorithm 2 is $O(n{Q}^{k^{\prime }-1})=O(n{Q}^{k-x-1})$. Hence, the time complexity of Algorithm 1 is bounded by:

$◀$

For some arbitrary value of $p$, let $S=(S_1,\mathrm{\dots },S_k)$ be an arbitrary feasible solution for the $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p)$. If $S$ breaks property 2, i.e. there exists a set $S_i$ in $S$ with $|S_i|>1$ containing an element $j>q$, we do the following. Let $S_m$ be a set with minimum sum¹⁰¹⁰10There could be multiple sets with the same (minimum) sum. and $u$ the smallest element of $S_i$. The following inequalities hold.

From these we can infer that, by moving $u$ from $S_i$ to $S_m$, the minimum sum cannot decrease and the maximum cannot increase. Thus, we move $u$ as described, yielding a solution $S^{\prime }$ with $ℛ(S^{\prime },A)\le ℛ(S,A)$. However, it might be the case that $S_m$ is $S_1$ and adding $u$ to it breaks the restrictions of $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$, so $S^{\prime }$ might not be a feasible solution for $(A,p)$. For the new solution $S^{\prime }$, define $p^{\prime }$ as the minimum among the maxima of its $k$ sets and call $S_1$ the set that contains $p^{\prime }$. Note that $S^{\prime }$ is a feasible solution for the $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p^{\prime })$.

If $S^{\prime }$ still breaks property 2 for $Q^{\prime }={\sum }_{i=1}^{p^{\prime }}{a}_i$ and $q^{\prime }=\max \{i\mid a_i\le Q^{\prime }\}$, apply the same process. By doing this repeatedly, $p$ cannot decrease and the ratio of the solution cannot increase. Note that $p$ cannot exceed $n-k+1$ with this process, so at some point $p$ will stop increasing. Let $p_f$ be this final value and define $Q_f,q_f$ accordingly for $p_f$. Repeating the process will at some point yield a solution that satisfies property 2 for the $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p_f)$.

Let $S^{\prime \prime }$ be the feasible solution for the $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p_f)$, derived from the process described in the previous paragraphs. $S^{\prime \prime }$ satisfies property 2 for values $Q_f,q_f$. If $S^{\prime \prime }$ breaks property 1, i.e. it contains a set $S_i$ consisting only of elements $j\le q_f$ and having sum $\mathrm{\Sigma }(S_i,A)\ge 2Q_f$, we apply the following transformation. Let $S_m$ be a set with minimum sum. Take the smallest element $j$ from $S_i$ and move it to $S_m$. Observe that $a_j\le Q_f$. Hence, the following inequalities hold.

From these we can infer that, by moving $j$ from $S_i$ to $S_m$, the minimum sum cannot decrease and the maximum cannot increase. We repeatedly apply this process until we end up with a solution satisfying property 1, just like we did in the previous paragraphs for property 2, since the same arguments hold regarding the increment of $p$ and the ratio not increasing. Furthermore, this transformation preserves property 2, as $p$ cannot decrease through this process and we only add elements to the set with the smallest sum (which cannot be a set containing an element $j>q$).

In conclusion, for any feasible solution for a $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p)$ that violates some property, we can find a feasible solution for another $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p_{new})$ that satisfies both properties and has equal or smaller ratio. Suppose we apply this to an optimal solution for a $k\text{-}{\mathrm{PART}}_{\mathrm{R}}$ instance $(A,p)$, with $p$ being perfect¹¹¹¹11Such a $p$ always exists, by definition. for the $k\text{-}\mathrm{PART}$ instance $A$. Since the ratio of the solution does not increase throughout the constructions described in this proof, any new $p^{\prime }$ obtained by the constructions must also be perfect and the solution obtained must be optimal for $(A,p^{\prime })$. $◀$

Let $p^{\ast }$ be one of the perfect elements guaranteed to exist by Theorem 18 for $A$ and $S^{\ast }$ be a respective optimal solution for $(A,p^{\ast })$ satisfying properties 1 and 2. The following lemmas indicate that we can prune certain values of $p$, without missing $S^{\ast }$. We define $x=n-q$. Intuitively, for $(A,p^{\ast })$, $x$ is the number of large elements that must be contained in singleton sets in $S^{\ast }$, according to Theorem 18.

Since $S_1$ cannot contain elements $j>q$, there are $k-1$ sets that can contain such elements. The number of these elements is $x$. If $x>k-1$, by the pigeonhole principle, every feasible solution contains a set with two or more of these elements. This contradicts property 2 of Theorem 18, therefore $p\ne p^{\ast }$. $◀$

Because , $S_1$ cannot contain $q$. Thus, there are at least $x+1=k$ elements that cannot be contained in $S_1$, with $k-1$ of them being greater than $q$. By the pigeonhole principle, every feasible solution contains a set with two or more elements, one of which is greater than $q$. This contradicts property 2 of Theorem 18, therefore $p\ne p^{\ast }$. $◀$