3
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented Nov 28, 2023 at 7:43
  • $\begingroup$ @gnasher729 Right. But I am mainly interested in instances with big items - how big should they be so that the problem is in P? $\endgroup$ Commented Nov 28, 2023 at 7:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.