3
$\begingroup$

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$.

This is a special case of the subset sum problem. Since there are at most $(r+1)(t+1)$ possible sums, one can just check all of them and find the maximum sum that is at most $C$. But this takes time $O(r t)$, while the size of the input - if it is given in binary - is $\log{(r t a b)}$.

Is there an algorithm that solves the problem in time polynomial in the size of the binary representation of the input?

$\endgroup$
4
  • $\begingroup$ There is a simple algorithm in $O(r+t)$, but it still doesn't achieve the bound you wanted. $\endgroup$
    – nir shahar
    Nov 18, 2021 at 18:23
  • $\begingroup$ There is also a simple algorithm that runs in time $O^*(\min\{r,t\})$, but that's still too slow (here the $O^*$ notation suppresses polynomial factors in the input size). $\endgroup$
    – Steven
    Nov 18, 2021 at 20:34
  • $\begingroup$ The ordinary subset sum problem would have an input size of r log a + t log b for the same problem, and can easily be solved in polynomial time. There are probably many problems in P, NP etc. where special cases can be encoded with much smaller input size and the solution time goes up relative to the input size. $\endgroup$
    – gnasher729
    Nov 19, 2021 at 10:20
  • 2
    $\begingroup$ This appears to be an integer program in two variables; have you considered Lenstra's algorithm for integer programming? $\endgroup$
    – kcsquared
    Nov 19, 2021 at 12:43

1 Answer 1

2
$\begingroup$

As kcsquared notes, this is an instance of integer linear programming (ILP) in two dimensions. Lenstra showed that ILP can be solved in polynomial time when the number of dimensions is constant; the special case of two dimensions was apparently proven earlier by Scarf. This proves that your program can be solved in polynomial time, as you were hoping.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.