Variant of Subset Sum Problem with Changing Bound

Question

Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that $$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$ $$s.t., \sum_{i\in S/\{t\}} a_i \leq k \cdot a_t,$$ where $a_t$ represents the smallest one of subset $S$.

Note that $a_t$ is the smallest of set $S$ and may be different for different set $S$. I am wondering whether this problem is still NP-complete. Any comments or suggestions will be very appreciated.

Answer 1

It's still NP-complete, via a reduction from the partition problem (in the form of: given a collection of $n$ positive numbers $x_i$, where $n$ is even, partition the numbers into two subsets with equal sums). This exact form of the partition problem is not one of the ones mentioned by Garey and Johnson (SP12); in particular they don't mention the constraint that the numbers be positive. But they do mention a variation of partition in which the numbers are paired and you have to use one from each pair. By adding the same positive number to both numbers in a pair you can make them all positive, and then by adding different large powers of two to different pairs you can get an instance where the one-from-each-pair constraint is the only way to solve it, and doesn't need to be specified as an explicit constraint.

In the partition problem, we can assume without loss of generality that $\sum x_i=1$, since multiplying or dividing the inputs by a scalar doesn't change the problem. We'll also assume that $n$ is even, since that's what you get from the reduction from the paired variation of partition. Thus, we are trying to find a subset whose sum is $1/2$. Note that, if there is such a subset, then its complement is also a solution; in particular, one of the two solutions has at least $n/2$ elements.

Given such a partition instance, set up an instance of the changing-bound problem with $T=2n$ input values: $n$ of them of the form $1+x_i$, and another $n$ of them that are all equal to $1$. Set $k=(3n-1)/2$. Because $k$ is so large, any near-optimal solution must include at least one of the values that is equal to $1$, so this will necessarily be the minimum value. The goal of the changing-bound problem is then to have the sum of the whole set (including its minimum) come as close as possible to $(3n+1)/2$ without exceeding it. If the partition problem has a solution, then we can turn it into a solution to the changing-bound problem that exactly reaches this goal of $(3n+1)/2$, by choosing a partition solution with at least $n/2$ elements and padding them with the desired number of $1$s. And conversely, if the changing-bound problem has a solution with the exact value $(3n+1)/2$, then the subset of this solution consisting of the values of the form $1+x_i$ also give a solution to the partition instance.