# Subset sum problem with big items

Consider the variant of the Subset Sum problem, where the input is a list of $$2 m + 1$$ positive integers of sum $$2 S$$, and the goal is to find a subset with the largest sum that is at most $$S$$. The problem is NP-hard in general, but it can be solved in polynomial time if the all inputs are 'big', that is, larger than $$B\cdot (1-1/3m)$$, where $$B$$ is the largest input and $$m$$ is the number of inputs.

Proof: under the above assumption, every set of $$m+1$$ inputs has sum larger than $$(m+1)\cdot B\cdot (1-1/3m) = (m+1-1/3-1/3m)B = (m+2/3-1/3m)B > (m+1/2)B$$. Since $$S \leq (m+1/2)B$$, the required subset cannot contain $$m+1$$ inputs .

On the other hand, every set of $$m$$ inputs has sum at most $$m B$$. But $$S > (m+1/2)(1-1/3m)B = (m+1/2-1/3-1/6m) = (m+1/6 - 1/6m)B > mB$$. Therefore, every set of $$m$$ inputs is feasible. Therefore, the optimal set is simply the set of $$m$$ largest items, which can obviously be found in polynomial time.

Note that we can slightly relax the lower bound, from $$B\cdot(1-1/3m)$$ to $$B\cdot (1-1/t m)$$ for some $$t>2$$, and a similar argument works to show that the problem is polynomial.

My goal is to find the exact "transition point" between subset-sum variants that are NP-hard, and those that can be solved in polynomial time. QUESTIONS:

• What is the smallest fraction $$r$$ such that, when all inputs are larger than $$r\cdot B$$, the subset-sum problem is in P?
• How to prove that, when the lower bound is smaller than $$r \cdot B$$, the problem is NP-hard?
• Your items are all very similar size, so any m items fit and m+1 don’t. You can add some tiny items, small enough to fit in the remaining space. Commented Nov 28, 2023 at 7:43
• @gnasher729 Right. But I am mainly interested in instances with big items - how big should they be so that the problem is in P? Commented Nov 28, 2023 at 7:46