  Consider positive integral solutions $x \in \mathbb{Z}^{n+1}$ to the equation
$a_0 x_0 + \ldots + a_n x_n = t$. In the so called unbounded subset sum
problem, the objective is to decide whether such a solution exists, whereas in
the Frobenius problem, the objective is to compute the largest $t$ such that
there is no such solution.
  In this paper we study the algorithmic complexity of the unbounded subset
sum, the Frobenius problem and a generalization of the problems. More
precisely, we study pseudo-polynomial time algorithms with a running time that
depends on the smallest number $a_0$ or respectively the largest number $a_n$.
For the parameter $a_0$, we show that all considered problems are
subquadratically equivalent to $(min,+)$-convolution, a fundamental algorithmic
problem from the area of fine-grained complexity. By this equivalence, we
obtain hardness results for the considered problems (based on the assumption
that an algorithm with a subquadratic running time for $(min,+)$-convolution
does not exist) as well as algorithms with improved running time. The proof for
the equivalence makes use of structural properties of solutions, a technique
that was developed in the area of integer programming.
  In case of the complexity of the problems parameterized by $a_n$, we present
improved algorithms. For example we give a quasi linear time algorithm for the
Frobenius problem as well as a hardness result based on the strong exponential
time hypothesis.
