<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-04-22T00:11:22.243Z
2016-04-22T00:11:22.243Z
David Eppstein
<p>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$. </p>

<p>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.</p>

<np-hardness><partition-problem><subset-sum>
Variant of Subset Sum Problem with Changing Bound
Tomlin
# Variant of Subset Sum Problem with Changing Bound

(Asked by: username_0 on 2016-04-18)

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.

**Tags:** np-hardness, partition-problem, subset-sum


---

## 1 answers

### Answer by username_1 on 2016-04-22. Score: 5

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.


---

