# On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius
Problem

Kim-Manuel Klein
University of Kiel
<EMAIL_ADDRESS>
###### Abstract

Consider positive integral solutions $x\in\mathbb{Z}_{\geq 0}^{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.

##  1 Introduction

Consider the integer program

$\displaystyle a_{0}x_{0}+\ldots+a_{n}x_{n}$ $\displaystyle=t$ (1)
$\displaystyle x\in\mathbb{Z}_{\geq 0}^{n+1}$ .

for a given set of numbers $a_{0},\ldots,a_{n},t\in\mathbb{Z}_{\geq 0}$.
Having only a single constraint, (1) is the most basic integer program in
standard form. In this paper we consider fundamental algorithmic problems
regarding (1). We call the numbers $a_{0},\ldots,a_{n}$ the _item sizes_ and
define the set of item sizes $S$ by $S=\\{a_{0},\ldots,a_{n}\\}$. Throughout
the paper we assume that the items are sorted by $a_{0}<a_{1}<\ldots<a_{n}$
and that $gcd(a_{0},\ldots,a_{n})=1$ (this property is not really necessary as
one can always divide by the gcd). We call $t$ the _target value_ and we say
that $t$ is a feasible target value for given $a_{0},\ldots,a_{n}$ if (1) is
feasible.

In the Unbounded SubsetSum problem the objective is to decide if (1) is
feasible, i.e. decide for given item sizes $S$ and target
$t\in\mathbb{Z}_{\geq 0}$ if $t$ is feasible. Formally it is defined by

Unbounded SubsetSum Input: Items $a_{0},\ldots,a_{n}\in\mathbb{Z}_{\geq 0}$
and $t\in\mathbb{Z}_{\geq 0}$. Objective: Decide whether (1) is feasible.

By a classical dynamic program that is being taught in undergraduate, the
problem can be solved in time $O(nt)$ [9].

In a related problem, the objective is to compute the largest $t$ such that
(1) is infeasible. This problem is intensively studied in the literature and
is referred to by different names like the coin problem, the postage-stamp
problem or the Frobenius problem (it was originally defined by Frobenius).

Frobenius Input: Items $a_{0},\ldots,a_{n}\in\mathbb{Z}_{\geq 0}$. Objective:
Compute the largest $t\in\mathbb{Z}_{\geq 0}$ such that (1) does not have a
solution.

The solution to the problem is called the _Frobenius number_ and we denote it
by $F(a_{0},\ldots,a_{n})$. In the case that the item sizes
$a_{0},\ldots,a_{n}$ are clear from the context, we will only write $F$. For
this problem, the property that $gcd(a_{0},\ldots,a_{n})=1$ is essential, as
$F(a_{0},\ldots,a_{n})$ would not be finite otherwise. It is easy to see that
$F$ is finite if $gcd(a_{0},\ldots,a_{n})=1$ and moreover $F\leq a_{n}^{2}$.

A natural generalization of both problems is a problem that computes the so
called residue table. The residue table was first considered by Brauer and
Shockley [11] already in 1962 in order to solve Frobenius. In this problem,
essentially, the feasibility for all target values $t$ is solved. We call the
problem AllTargets.

AllTargets Input: Items $a_{0},\ldots,a_{n}\in\mathbb{Z}_{\geq 0}$. Objective:
Compute $a[0],\ldots,a[n-1]$, such that $\displaystyle
a[i]=\min\\{t\in\mathbb{Z}_{\geq 0}\mid t\equiv i\bmod a_{0}\text{ and $t$ is
a feasible solution of (\ref{IP1})}\\}.$

Having a solution of AllTargets at hand, one can decide in constant time if
any given target $t$ is feasible (assuming that any element $a[i]$ in the
sequence $a$ can be accessed in constant time). This is because

$\displaystyle t\text{ is feasible}\quad\Leftrightarrow\quad t\geq a[t\bmod
a_{0}].$

Note that in the case that $t>a[t\bmod a_{0}]$ a solution for target $t$ can
be obtained by adding multiples of $a_{0}$ to the solution for target
$a[t\bmod a_{0}]$ (which by definition exists). By the same argumentation, the
Frobenius number can be determined from the residue table $a$ in $O(a_{0})$
time. The Frobenius number $F$ is

$\displaystyle F=\max_{i}\\{a[i]\\}-a_{0}.$

Many algorithms in the literature that solve Unbounded SubsetSum or Frobenius
actually solve the more general problem of AllTargets and then extract the
respective solution for Frobenius or Unbounded SubsetSum from the table. In
this context one might ask if the AllTargets problem is actually
computationally equivalent to Unbounded SubsetSum and Frobenius or if it is
harder to compute the more general problem of determining the complete residue
table. We have a partial answer on this question in this paper.

In general, Unbounded SubsetSum and Frobenius are classical (weakly) NP-
complete problems [26, 28], that is, if we assume that the given numbers
$a_{0},\ldots,a_{n},t$ are encoded in binary. In this paper we study pseudo-
polynomial time algorithms with a running time that depends on the smallest
item size $a_{0}$ or the largest item size $a_{n}$.

###  1.1 Related Results

There are two different communities involved in studying the Unbounded
SubsetSum and the Frobenius problem. On the one hand, there is the community
that considers variants of subset sum problems. On the other hand there is the
community which studies the Frobenius problem from various angles, which
includes bounds for the Frobenius number, algorithmic complexity of the
problem as well as practical fast algorithms.

#### Subset Sum

One of the most fundamental problems in computed science is the (bounded)
subset sum problem where the objective is to find a subset of a given
(multi-)set of $n$ items such that there total sum equals $t$. This is
equivalent to an integer program as in (1), where additional upper bounds on
the variables are given. Unbounded SubsetSum is in this sense a special case
of the (bounded) subset sum problem, where the multiplicities of each item
size are sufficiently large, i.e. $\geq t$. Using a classical dynamic program
by Bellman from 1957, the (bounded) subset sum problem can be solved in time
$O(nt)$. This algorithm was improved by Koiliaris and Xu [24] who gave an
algorithm with a running time of $\tilde{O}(\sqrt{n}t)$ (omitting logarithmic
factors) and then further by a breakthrough result of Bringmann [12] who gave
an algorithm with a running time of $\tilde{O}(n+t)$. In that work, Bringmann
also developed an algorithm for Unbounded SubsetSum with a running time of
$O(t\log t)$. Jansen and Rohwedder [22] showed later that there is an
algorithm with a running time $O(a_{n}\log^{2}a_{n})$ for Unbounded SubsetSum
for the stronger parameter $a_{n}$. Assuming the strong exponential time
hypothesis (SETH), it was shown that the existing algorithms are actually
optimal as Abboud et al. [1] proved that there is no algorithm for subset sum
or Unbounded SubsetSum with a running time of $O(t^{1-\epsilon})$ for any
$\epsilon>0$.

The complexity of Unbounded SubsetSum regarding the parameter $a_{0}$ was open
so far. In the hard instance that was used in [1] all items
$a_{0},\ldots,a_{n}$ and $t$ differ only by a factor of $2$ and therefore only
an algorithm with a running time of $O(a_{0}^{1-\epsilon})$ can be excluded.

#### The Frobenius Problem

The Frobenius problem is an intensively studied problem in the literature.
Since we can not cover all its aspects here, we refer to the monograph of
Ramirez-Alfonsin [2] for a general overview. The book covers over 400 sources
that are concerned with the problem.

In the case that $n=2$, the Frobenius number $F$ can be easily determined by
the formula $F=a_{0}a_{1}-a_{0}-a_{1}$. However for $n>2$ there is no formula
but several upper and lower bounds are known for $F$ (see for example [6,
19]). A bound that we make use of in this paper is due to Erdös and Graham
[18] which states that

$\displaystyle
F(a_{0},\ldots,a_{n})\leq\frac{2a_{n-1}a_{n}}{n+1}-a_{n}=O\big{(}\frac{a_{n}^{2}}{n}\big{)}.$

As mentioned, the Frobenius problem is NP-complete and hence we can not expect
a polynomial time algorithm. However, many pseudo-polynomial time algorithms
have been studied having a running time which depends on the input parameters.
The most relevant result for our paper here is the result of Böcker and Lipták
[10]. They developed an algorithm solving AllTargets and therefore also
Frobenius and Unbounded SubsetSum with a running time of $O(na_{0})$. Based on
the Round Robin procedure, they presemt a very elegant dynamic program
computing the residue table. By this, Böcker and Lipták improved upon several
known existing pseudo-polynomial time algorithms for the Frobenius problem
(see Chapter 1 in [2]). The algorithm of Nijenhuis [27] for example has a
running time of $O(a_{0}(n+\log a_{0}))$. Nijenhuis used Dijkstras algorithm
in the weighted Cayley graph of the group $(\mathbb{Z}_{a_{0}},+)$ to compute
the residue table. The performance of several pseudo-polynomial time
algorithms for the problem has been tested in practice [8].

The mentioned pseudo-polynomial time algorithms are efficient in the case that
the input numbers are small. There are also algorithms for Frobenius in the
case that $n$ is small. For example, for three coins, Greenberg [20] developed
an algorithm with a running time of $O(\log a_{0})$. Kannan [23] showed in the
end that there is a polynomial time algorithm for any constant $n$. Other
practically efficient algorithms have been developed that are efficient if $n$
is small (see for example [15, 29]).

###  1.2 Our Results:

In this paper we prove several algorithmic results as well as hardness results
based the above mentioned assumption for $(min,+)$-convolution (which we
denote by MinConv) and the SETH. Concerning parameterization by $a_{0}$, we
prove the following theorem, which shows that all our considered problems are
subquadratically equivalent.

######  Theorem 1.

The following statements are equivalent:

  1. 1.

MinConv can be solved in time $O(n^{2-\epsilon})$.

  2. 2.

Unbounded SubsetSum can be solved in time $O(a_{0}^{2-\epsilon})$.

  3. 3.

The Frobenius problem can be solved in time $O(a_{0}^{2-\epsilon})$.

  4. 4.

AllTargets can be solved in time $O(a_{0}^{2-\epsilon})$.

More precisely, we show in Theorem 2 that AllTargets can be solved by using
only at most $\lceil\log\log a_{0}\rceil$ times $(min,+)$-convolution as a
subroutine. Using the algorithm of Williams [30], we obtain a faster algorithm
for the considered problems with a running time of
$\frac{a_{0}^{2}}{2^{\Omega(\log a_{0})^{1/2}}}$ beating the best known
algorithm of Böcker and Lipták [10] in the case that
$n\in\Omega(\frac{a_{0}}{\log^{c}a_{0}})$ for any constant $c$. The theorem
relies on a structural result for solutions of (1) that we show in Lemma 1
which is of interest by itself. This type of structural result was first used
to bound the number of non-zero components of feasibility IPs.

Concerning parameterization by the largest item size $a_{n}$, we present the
following results:

  * •

Algorithm 1 solving Unbounded SubsetSum with a running time of $O(a_{n}\log
a_{n}\cdot\log(\frac{F}{a_{n}}))$ improving upon the algorithm by Jansen and
Rohwedder [22] in the case that the Frobenius number $F$ is small, i.e.
$F<<a_{n}^{2}$. For example, for average case instances the expected Frobenius
number is rather small (see [5]).

  * •

Algorithm 2 solving Frobenius with a running time of $O(a_{n}\log
a_{n}\cdot\log(\frac{F}{a_{n}}))$. To our best knowledge this is the first
algorithm solving the problem in quasi linear time by an input parameter. It
beats the algorithm obtained by Theorem 1 in the case that $a_{n}<<a_{0}^{2}$.

  * •

Algorithm 4 solving AllTargets with a running time of
$O(a_{n}^{3/2}\log^{1/2}a_{n})$. To our best knowledge the paramterized
complexity of the problem has not been considered yet with respect to the
parameter $a_{n}$.

  * •

Based on the existing hardness result by Abbout et al. [1], Theorem 10 proves
hardness for Frobenius for the parameter $a_{n}$ and therefore shows that
Algorithm 2 is nearly optimal (assuming SETH).

###  1.3 Hardness Assumptions

A fundamental problem in the area of fine grained complexity is
$(min,+)$-convolution which we denote by MinConv.

MinConv Input: Sequences $(a[i])_{i=0}^{n-1}$ and $(b[i])_{i=0}^{n-1}$.
Objective: Compute a sequence $(c[i])_{i=0}^{n-1}$, such that $\displaystyle
c[k]=\min_{i+j=k}(a[i]+b[j]).$

It is assumed that there does not exist a truly subquadratic algorithm for the
problem.

Assumption: MinConv can not be solved in time $O(n^{2-\epsilon})$ for any
$\epsilon>0$.

This assumption is the base of several lower bounds in fine-grained complexity
([7, 14, 25]). Cygan et al.[14] showed equivalence of MinConv to several
problems including the unbounded knapsack problem parameterized by $a_{n}$ \-
a problem related to Unbounded SubsetSum.

One of the most basic hardness assumption that we make use of is based on the
$k$-SAT problem, where the objective is to decide the feasibility of a boolean
formula in conjunctive normal form having at most $k$ variables per clause.
The strong exponential time hypothesis (SETH) was stated by Impagliazzo and
Paturi [21] and is has been used since for dozens of problems in Parameterized
Complexity and for problems within P to show lower bounds.

Assumption (SETH): There does not exist an algorithm for $k$-SAT with a
running time of $O(2^{(1-\epsilon)n})$ for any $\epsilon>0$.

##  2 Complexity of Parameterization by $a_{0}$

In this section we prove Theorem 1 regarding the equivalence of MinConv to
AllTargets, Unbounded SubsetSum and the Frobenius problem when parameterized
by the smallest item size $a_{0}$.

MinConvThm.2AllValuesFrobeniusThm.4SubsetSumThm.3SubAdditivity Testing[14]
Figure 1: Overview of the reductions. An arrow from $A$ to $B$ denotes a
reduction from problem $A$ to problem $B$.

###  2.1 Structural Properties of Solutions

Before we show Theorem 1, we prove a structural result regarding the existence
of solutions of (1) with a specific shape. The shown structural property will
then be of use in Theorem 2.

The proof of the structural result relies on a technique that was developed in
the area of integer programming showing the existence of solutions of bounded
support [16]. The support $supp(x)$ of a solution $x$ is the set of non-zero
components.

######  Lemma 1.

Assuming that (1) is feasible, then there exists a solution $x$ of (1) with

$\displaystyle\prod_{i=1}^{n}(x_{i}+1)\leq a_{0}.$

###### Proof.

Let $x\in\mathbb{Z}_{\geq 0}^{n}$ be a solution of (1) that is
lexicographically maximal. We will show that for this solution
$\prod_{i=1}^{n}(x_{i}+1)\leq a_{0}$ holds.

Suppose by contradiction that $\prod_{i=1}^{n}(x_{i}+1)>a_{0}$. By the
pigeonhole principle there exist two distinct subvectors
$x^{\prime},x^{\prime\prime}\leq x$ with

$\displaystyle a^{T}x^{\prime}\equiv a^{T}x^{\prime\prime}\bmod a_{0}$

and hence $a^{T}x^{\prime}=a^{T}x^{\prime\prime}+ka_{0}$ for some
$k\in\mathbb{Z}$. Without loss of generality we assume that $k\geq 0$
(otherwise we would exchange $x^{\prime}$ and $x^{\prime\prime}$). If $k=0$ we
assume that $x^{\prime}$ is lexicographically smaller than $x^{\prime\prime}$.
The solution $x$ can now be modified to obtain a solution
$y\in\mathbb{Z}_{\geq 0}^{n}$ by

$\displaystyle y=x+x^{\prime\prime}-x^{\prime}+ke_{0}.$

The solution $y$ is feasible since

$\displaystyle
t=a^{T}x=a^{T}x+a^{T}(x^{\prime\prime}-x^{\prime}+ke_{0})=a^{T}y,$

as by definition

$\displaystyle
a^{T}(x^{\prime\prime}-x^{\prime}+ke_{0})=a^{T}(x^{\prime\prime}-x^{\prime})+ka_{0}=0,$

holds, where $e_{0}$ is the $0$-th unit vector. Furthermore $y\geq 0$ holds as
$x-x^{\prime}\geq 0$ and therefore we can conclude that $y$ is a feasible
solution of IP (1).

If $k>0$ then $y_{0}=x_{0}+k$ and hence the solution $y$ is lexicographically
larger than $x$, which is a contradiction to the assumption. If $k=0$ and
hence $x^{\prime}$ is lexicographically smaller than $x^{\prime\prime}$ there
exists a component $i\in(supp(x^{\prime})\cup supp(x^{\prime\prime}))$ such
that $x^{\prime\prime}_{i}>x^{\prime}_{i}$ and
$x^{\prime}_{j}=x^{\prime\prime}_{j}$ holds for all $j<i$. However, this
implies again that $y$ is lexicographically larger than $x$ which is a
contradiction to the assumption. Therefore $\prod_{i=1}^{n}(x_{i}+1)\leq
a_{0}$ holds. ∎

The following corollary shows the existence of a solution of (1) with bounded
support. It follows directly from the previous lemma. The same statement was
previously already shown by Aliev et al. [3] using a different proof
technique. In their proof they use a geometric volume argument in combination
with Minkowski’s first theorem from the geometry of numbers. Before that Aliev
et al.[4] had also shown a weaker bound of $\log(a_{n})+1$.

######  Corollary 1.

There exists a solution $x$ of (1) with

$\displaystyle|supp(x)|\leq\log(a_{0})+1.$

###### Proof.

By Lemma 1 there exists a solution $x$ of (1) with

$\displaystyle 2^{|supp(x)\setminus\\{0\\}|}\leq\prod_{i=1}^{n}(x_{i}+1)\leq
a_{0}.$

We obtain that $|supp(x)|\leq\log(a_{0})+1$. ∎

###  2.2 Solving AllTargets by MinConv

In order to solve AllTargets we use a min-convolution operation, where the
indices of the sequences are computed $\bmod n$. Let the _modulo-min-
convolution_ $a\oplus_{n}b$ of two sequence $(a[i])_{i=0}^{n-1}$ and
$(b[i])_{i=0}^{n-1}$ be defined by

$\displaystyle(a\oplus_{n}b)[k]=\min_{i+j\equiv k\bmod n}a[i]+a[j].$

The modulo-min-convolution can easily be computed using the classical
convolution on modified sequences $\bar{a}$ and $\bar{b}$ of length $2n$
defined by

$\displaystyle\bar{a}[i]=a[i\bmod n]\quad\text{ for }i=0,\ldots,2n-1$
$\displaystyle\bar{b}[i]=a[i\bmod n]\quad\text{ for }i=0,\ldots,2n-1.$

We compute the sequence $\bar{c}$ using classical min-convolution, i.e.

$\displaystyle\bar{c}=\bar{a}\oplus\bar{b}.$

The sequence $c=a\oplus_{n}b$ is then obtained by

$\displaystyle c[i]=\min\\{\bar{c}[i],\bar{c}[i+n]\\}\quad\text{ for
}i=0,\ldots,n-1.$

Applying the mod-min-convolution repeatedly to a sequence $(a[i])_{i=0}^{n-1}$
yields a sequence $a^{*}$ with

$\displaystyle a^{*}=a\oplus_{n}a\oplus_{n}\cdots,$

where $a^{*}=a^{*}\oplus_{n}a$ holds. For this sequence there exist no indices
$i,j$ with $a^{*}[i]+a^{*}[j]<a^{*}[i+j\bmod n]$. In this sense $a^{*}$ is the
_transitive mod-min-convolution closure_ of the sequence $a$. It is easy to
see that a solution to the AllTargets problem is actually the transitive mod-
min-convolution closure of the sequence $(a[i])_{i=0}^{a_{0}-1}$ defined by

$\displaystyle a[i]=\min\\{a_{j}\mid a_{j}\equiv i\bmod a_{0}\\}.$

In the following theorem we show that $a^{*}$ can be computed by using only
$\lceil\log\log a_{0}\rceil$ many mod-min-convolution operations.

######  Theorem 2.

An algorithm for MinConv with a running time of $T(n)$ implies an algorithm
with a running time of

$\displaystyle\lceil\log\log a_{0}\rceil\cdot T(a_{0})+O(a_{0}\log a_{0})$

for AllTargets.

###### Proof.

Define the set $V$, which consists of the set of item sizes $S$ and multiples
of $a_{i}\in S$ which are powers of $2$, i.e.

$\displaystyle V=\bigcup_{1\leq i\leq n}\left(\bigcup_{0\leq
j\leq\log(a_{0})}2^{j}a_{i}\right)$

Obviously, every element of $V$ is a feasible target value and also every sum
of elements of $V$ is a feasible target value.

Define the sequence $A$ of length $a_{0}$ by

$\displaystyle A[i]=\min\\{t\in V\mid t\equiv i\bmod a_{0}\\}.$

The sequence $A$ can be computed in $O(a_{0}\log a_{0})$ time in a
straightforward way. Starting with $a_{1}$, each item $a_{i}$ is iteratively
multiplied by $2$ and the value $2^{j}a_{i}$ is stored in $A[2^{j}a_{i}\bmod
a_{0}]$ if it is smaller than its current content (the sequence is initialized
by infinity values).

Compute the sequence

$\displaystyle
A^{*}=\underbrace{A\oplus_{a_{0}}\ldots\oplus_{a_{0}}A}_{\lfloor\log
a_{0}\rfloor}$

which is obtained by a $\lfloor\log a_{0}\rfloor$-fold mod-convolution of $A$.

Claim: The sequence $A^{*}$ is the solution to the AllTargets problem.

Clearly, each element $A^{*}[i]$ is a feasible target value with
$A^{*}[i]\equiv i\bmod a_{0}$ as it is contained in the sum of elements of
$V$.

On the other hand, let $t_{i}$ be the minimum feasible target value with
$t_{i}\equiv i\bmod a_{0}$. By Lemma 1 we know that for each
$t_{i}\in\mathbb{Z}_{\geq 0}$ there exists a solution $x\in\mathbb{Z}_{\geq
0}^{n}$ with $\sum_{i=1}^{n}\log(x_{i}+1)\leq\log a_{0}$ (note that $x_{0}=0$
otherwise, $t_{i}$ would not be minimal). This implies that
$t_{i}=x_{1}a_{1}+\ldots+a_{n}x_{n}$ can be written by the sum of

$\displaystyle\sum_{i=1}^{n}\log(x_{i}+1)\leq\log a_{0}$

many elements of $V$ (by binary encoding, each multiplicity $x_{i}$ of an
element $a_{i}$ is contained in the sum of at most $\log(x_{i}+1)$
multiplicity elements $2^{j}a_{i}$ contained in $V$). Therefore, every $t_{i}$
is contained in the $\lfloor\log a_{0}\rfloor$-fold addition of $V$, i.e.
$t_{i}\in\underbrace{V\oplus_{a_{0}}\ldots\oplus_{a_{0}}V}_{\lfloor\log
a_{0}\rfloor}$ which is equivalent to $\lfloor\log a_{0}\rfloor$-fold Min-
Convolution of $A$ and hence $t_{i}=A^{*}[i]$ which proves the claim.

By using a binary exponentiation argument we can reduce the number of calls to
the mod-convolution procedure further and compute $A^{*}$ more efficiently.
Therefore, define

$\displaystyle
B^{(i)}=\underbrace{A\oplus_{a_{0}}\ldots\oplus_{a_{0}}A}_{2^{i}}.$

The sequences $B^{(i)}$ can be computed efficiently using $i$ calls to the
mod-convolution procedure by $B^{(1)}=A$ and
$B^{(i)}=B^{(i-1)}\oplus_{a_{0}}B^{(i-1)}$ for $i>1$. Finally, $A^{*}=B^{r}$
is obtained for $r\geq\lceil\log\log a_{0}\rceil$. Note that as the entries of
$A$ are minimal, we have that $A^{*}\oplus_{a_{0}}A=A^{*}$ and therefore it
does not hurt to apply too many mod-convolutions on $A$. ∎

Using the famous algorithm of Williams [30] to solve MinConv in time
$\frac{n^{2}}{2^{\Omega(\log n)^{1/2}}}$ yields improved algorithms for the
considered problems. By this we improve upon the algorithm of Böcker and
Lipták [10] in the case that the number of items $n$ is not small, i.e.
$n\in\Omega(\frac{n}{\log^{c}n})$ for any constant $c$ (note that the term
$2^{\Omega(\log n)^{1/2}}$ grows asymptotically faster than any
polylogarithmic function).

######  Corollary 2.

The Unbounded SubsetSum, the Frobenius and the AllTargets problem can be
solved with a running time of

$\displaystyle\frac{a_{0}^{2}}{2^{\Omega(\log a_{0})^{1/2}}}.$

Furthermore, it is known that MinConv can be solved for random instances in
near linear expected time [13]. Using this algorithm as a subroutine might
yield a very efficient practical algorithm that solves AllTargets.

###  2.3 Hardness of Unbounded SubsetSum and Frobenius

In the following we show hardness of the Unbounded SubsetSum and the Frobenius
problem by a reduction from SubAdditivity Testing, a problem that is known to
be subquadratically equivalent to MinConv[14]. The problem of SubAdditivity
Testing is to decide for a given sequence $(a[i])_{i=0}^{n-1}$ if there exist
indices $i,j$ such that $a[i]+a[j]<a[i+j\bmod n]$. We consider the modulo
version of the problem which we call Mod-SubAdditivity Testing.

Mod-SubAdditivity Testing Input: Sequence $(a[i])_{i=0}^{n-1}$ Objective:
Decide whether there exist indices $i,j$ such that $a[i]+a[j]<a[i+j\bmod n]$.

In other words, the problem is to decide if a given sequence $a$ is idempotent
under a mod-min-convolution operation, i.e. if $a\oplus_{n}a=a$.

It is easy to see that Mod-SubAdditivity Testing is subquadratically
equivalent to SubAdditivity Testing.

######  Proposition 1.

If there exists an algorithm with a running time of $T(n)$ for SubAdditivity
Testing then there exists an algorithm with a running time of $T(2n)+O(n)$ for
Mod-SubAdditivity Testing and vice versa.

###### Proof.

Given is a sequence $(a[i])_{i=0}^{n-1}$ in the Mod-SubAdditivity Testing
problem. Construct a sequence $(b[i])_{i=0}^{2n-1}$ of double length defined
by

$\displaystyle b[i]=a[i\bmod n]\quad\text{ for }i=1,\ldots,2n$

There exist indices $i,j$ such that $b[i]+b[j]<b[i+j]$ if and only if there
exist indices $i,j\leq n$ with $a[i]+a[j]<a[i+j\bmod n]$. Therefore, an
algorithm of running time $T(n)$ for the SubAdditivity Testing problem implies
an algorithm of running time $T(n)+O(n)$ for the Mod-SubAdditivity Testing
problem.

On the other hand, let $(a[i])_{i=1}^{n}$ be a sequence in the SubAdditivity
Testing problem. Construct a sequence $(b[i])_{i=1}^{2n}$ of double length
defined by

$\displaystyle b[i]=\begin{cases}a[i]&\text{ for $i\leq n$}\\\ -\infty&\text{
otherwise.}\end{cases}$

There exist indices $i,j$ such that $b[i]+b[j]<b[i+j]$ if and only if there
exist indices $i,j\leq n$ with $a[i]+a[j]<a[i+j]$. Therefore, an algorithm of
running time $T(n)$ for the Mod-SubAdditivity Testing problem implies an
algorithm of running time $T(n)+O(n)$ for the SubAdditivity Testing problem. ∎

In the following theorem we show the reduction of Mod-SubAdditivity Testing
(respectively SubAdditivity Testing) to Unbounded SubsetSum.

######  Theorem 3.

An algorithm for Unbounded SubsetSum with a running time of $T(a_{0})$ implies
an algorithm with a running time of $T(n)+O(n)$ for SubAdditivity Testing.

###### Proof.

Given is a sequence $a[1],\ldots,a[n-1]$. Since $a[0]+a[i]\geq a[i+0]$ the
entry $a[0]$ does not need to be considered as it can not be used to violate
the modular-subadditivity property of a sequence.

The items of the Unbounded SubsetSum instance are defined by

$\displaystyle a_{0}$ $\displaystyle=2n$ (2) $\displaystyle a_{i}$
$\displaystyle=a_{0}a[i]+2i\qquad\qquad\qquad\text{for $i=1,\ldots,n-1$}$
$\displaystyle\bar{a}_{i}$ $\displaystyle=a_{0}(M-a[i])-2i-1\qquad\text{for
$i=1,\ldots,n-1$},$

where $M$ is defined by $M=2(\max_{i\in\\{1,\ldots,n-1\\}}a[i]+n)$. We define
the target value $t$ by

$\displaystyle t=a_{0}(M-1)-1.$

Suppose that the sequence $a$ is not modulo-subadditive. Then we can build a
solution of (1) in the following way: Given are indices $i,j$ with
$a[i]+a[j]<a[i+j\bmod a_{0}]$. Summing up the item sizes of $\bar{a}_{(i+j\mod
p)},a_{i}$ and $a_{j}$ we obtain that

$\displaystyle\quad\bar{a}_{(i+j\bmod p)}+a[i]+a[j]$
$\displaystyle=\,a_{0}(M-a[i+j\bmod
a_{0}])-2(i+j)-1+a_{0}a[i]+2i+a_{0}a[j]+2j$
$\displaystyle=\,a_{0}(M-a[i+j\bmod a_{0}]+a[i]+a[j])-1$
$\displaystyle=\,a_{0}(M-r)-1,$

for some $r\geq 1$. Hence $\bar{a}_{(i+j\mod p)}+a_{i}+a_{j}+ra_{0}=t$ which
proves feasibility of (1).

In the following we show that the converse is also true, i.e. if there exists
a solution of (1) then the sequence $a$ is not modulo-subaddtive.

Observation 1: A feasible solution of $(\ref{IP1})$ has to contain exactly one
item $\bar{a}_{i}$.
Since $t<M$ and every item $\bar{a}_{i}>M/2$, a feasible solution can contain
at most one item $\bar{a}_{i}$. On the other hand, since every item $a_{i}$ is
even and $a_{0}$ is also even, a sum with indices $I\subset[n-1]$ of items
fulfills $\sum_{i\in I}a_{i}\equiv 2y\bmod a_{0}$ for some
$y\in\mathbb{Z}_{a_{0}}$. This implies that $\sum_{i\in I}a_{i}\not\equiv
t\equiv-1\bmod a_{0}$. Therefore, a feasible solution has to contain at least
one item $\bar{a}_{i}$.

Observation 2: Consider a feasible solution of (1) using one item
$\bar{a}_{p}$ and items $\\{a_{i}\mid i\in I\\}$ for some $I\subseteq[n-1]$.
Then $p\equiv\sum_{i\in I}i\bmod a_{0}$ holds.
Because of the feasibility, we know that $\bar{a}_{p}+\sum_{i\in I}i\equiv
t\bmod a_{0}$, which implies

$\displaystyle\bar{a}_{p}+\sum_{i\in I}i$ $\displaystyle\equiv t\bmod a_{0}$
$\displaystyle\Leftrightarrow\quad-2p-1+\sum_{i\in I}2i$
$\displaystyle\equiv-1\bmod a_{0}$
$\displaystyle\Leftrightarrow\quad\sum_{i\in I}2i$ $\displaystyle\equiv
2p\bmod a_{0}$ $\displaystyle\Leftrightarrow\quad\sum_{i\in I}i$
$\displaystyle\equiv p\bmod a_{0}$

Using the observations above, we can now show that there exists a feasible
solution of (1) only if the sequence $a[1],\ldots,a[n-1]$ is not modulo-
subadditive.

Suppose that there exists a feasible solution of (1). Then by Observation 1
and 2 the solution uses a single item $\bar{a}_{p}$ and a set of items
$\\{a_{i}\mid i\in I\\}$ for some $I\subseteq[n-1]$ with $p\equiv\sum_{i\in
I}i\bmod a_{0}$. The solution is feasible only if

$\displaystyle\bar{a}_{p}+\sum_{i\in I}a_{i}$ $\displaystyle\leq t$
$\displaystyle\Leftrightarrow\quad a_{0}(M-\bar{a}[p]+\sum_{i\in I}a[i])-1$
$\displaystyle\leq a_{0}(M-1)-1$
$\displaystyle\Leftrightarrow\quad-a[p]+\sum_{i\in I}a[i]$
$\displaystyle\leq-1$ $\displaystyle\Leftrightarrow\quad\sum_{i\in I}a[i]$
$\displaystyle<a[p]$

This implies that there exist indices $i_{1},\ldots,i_{|I|}$ with
$i_{1}+\ldots+i_{|I|}\equiv p\bmod a_{0}$ such that
$a[i_{1}]+\ldots+a[i_{l}]<a[p]$. Note that $I$ can not be the empty set as
there is no item $\bar{a}_{p}$ with $\bar{a}_{p}\equiv t\bmod a_{0}$. Also
$|I|\neq 1$ holds as

$\displaystyle\bar{a}_{p}+a_{p}=a_{0}M-1>t.$

For $|I|=2$ we know there exist indices $i,j\in I$ with $a[i]+a[j]<a[i+j]$ and
therefore the sequence $a[1],\ldots a[n-1]$ is not mod-subadditive. In the
case of $|I|>2$ we can set $i=i_{1}$ and $j=i_{2}+\ldots+i_{|I|}\bmod a_{0}$.
Hence, either $a[j]<a[i_{2}]+\ldots+a[i_{|I|}]$ holds and we can proceed
inductively with the smaller index set $I^{\prime}=\\{i_{2},\ldots,i_{|I|}\\}$
or

$\displaystyle a[i+j\bmod a_{0}]>a[i_{1}]+a[i_{2}]+\ldots+a[i_{|I|}]\geq
a[i]+a[j]$

holds and hence mod-subadditivity is violated for indices $i$ and $j$. ∎

Taking a close look at instance (2) yields the same statement for Frobenius.

######  Theorem 4.

An algorithm for the Frobenius problem with a running time of $T(a_{0})$
implies an algorithm with a running time of $T(n)+O(n)$ for SubAdditivity
Testing.

###### Proof.

Given is the sequence $a[0],\ldots,a[n-1]$. We define the instance of item
sizes for the Frobenius problem just as in the previous Theorem 3:

$\displaystyle a_{0}$ $\displaystyle=2n$ $\displaystyle a_{i}$
$\displaystyle=a_{0}a[i]+2i\qquad\qquad\qquad\text{for $i=1,\ldots,n-1$}$
$\displaystyle\bar{a}_{i}$ $\displaystyle=a_{0}(M-a[i])-2i-1\qquad\text{for
$i=1,\ldots,n-1$},$

We will show that the frobenius number of this instance is $<a_{0}M-1$ if and
only if the sequence $a$ is not mod-subadditive.

Observe in the table below that for every target value $t\not\equiv-1\bmod
a_{0}$ there is an item $a_{i}$ or $\bar{a}_{i}$ such that $t\equiv a_{i}\bmod
a_{0}$ (if $t$ is even) or $t\equiv\bar{a}_{i}\bmod a_{0}$ (if $t$ is odd).

Item $\mod a_{0}$ | $0$ | $1$ | $2$ | $3$ | $4$ |  | $\cdots$ |  | $2n-4$ | $2n-3$ | $2n-2$ | $2n-1$
---|---|---|---|---|---|---|---|---|---|---|---|---
Item | $a_{0}$ | $\bar{a}_{n-1}$ | $a_{1}$ | $\bar{a}_{n-2}$ | $a_{2}$ |  | $\cdots$ |  | $a_{n-2}$ | $\bar{a}_{1}$ | $a_{n-1}$ |

Since the item sizes $a_{i}$ and $\bar{a}_{i}$ are $<a_{0}M-1$ every instance
with a target value $t\not\equiv-1\bmod a_{0}$ has a solution $<a_{0}M-1$.
Consider a target value $t\equiv-1\bmod a_{0}$: According to the proof of the
previous theorem there exists a solution for $t=a_{0}(M-1)-1$ if and only if
the sequence $a$ is not mod-subadditive. This implies that the frobenius
number of the instance is $<a_{0}M-1$ if and only if the sequence $a$ is not
mod-subadditive. ∎

##  3 The Complexity of Parameterization by $a_{n}$

In this section, we present algorithms for Unbounded SubsetSum, Frobenius and
AllTargets parameterized by the largest item size $a_{n}$. An algorithm for
Unbounded SubsetSum with a running time of $O(a_{n}\log^{2}a_{n})$ was already
known. The algorithm by Jansen and Rohwedder [22] solves general feasibility
IPs for given matrix $A\in\mathbb{Z}^{m\times n}$ and vector
$b\in\mathbb{Z}^{m}$ of the form

$\displaystyle Ax=b$ $\displaystyle x\in\mathbb{Z}_{\geq 0}^{n}$

with a running time of
$O((\sqrt{m}\left\|A\right\|_{\infty})^{m}\log\left\|A\right\|_{\infty}\cdot\log(\left\|A\right\|_{\infty}+\left\|b\right\|_{\infty}))+O(nm)$.
Using this algorithm for $m=1$ in combination with the proximity result of
Eisenbrand and Weismantel [17] in order to reduce $t$ (i.e. $t\leq a_{n}^{2}$)
leads to the mentioned running time for solving Unbounded SubsetSum.

In Section 3.1 we describe a modified and simplified version of the algorithm
by Jansen and Rohwedder [22] for solving Unbounded SubsetSum with a running
time of $O(a_{n}\log^{2}a_{n})$. In contrast to their algorithm, our algorithm
computes all feasible target values for a certain fixed set of intervals of
length $a_{n}$. This has the advantage that our algorithm is able to detect if
the Frobenius number of the instance is exceeded and terminates. By this we do
not need to use the integer programming proximity to reduce the target value
$t$ and instead use a bound on the Frobenius number which is in general
better. Therefore, our modified algorithm improves upon the running time if
$F<a_{n}^{2}$. However, the main reason why we present this version of the
algorithm is that we can show in Section 3.2, that our modified algorithm can
be easily adapted to compute a solution of the Frobenius problem.

In the algorithm, we compute the _sumset_ $S+T$ of two sets
$S,T\subset\mathbb{Z}$ defined by

$\displaystyle S+T=\\{s+t\mid s\in S,t\in T\\}.$

For two sets $S\subseteq I\cap\mathbb{Z}$ and $T\subseteq
I^{\prime}\cap\mathbb{Z}$ that are contained in intervals $I,I^{\prime}$ of
size $n$, it is well known that the sumset $S+T$ can be computed in time
$O(n\log n)$. This can done by a reduction to boolean convolution which can be
solved by an FFT approach (see also [22, 12]).

Define the intervals

$\displaystyle I^{(j)}=((j-1)a_{n},ja_{n}]$

and let $A^{(j)}$ be the set of all feasible target values within the interval
$I^{(j)}$, i.e.

$\displaystyle A^{(j)}=\\{t\in I^{(j)}\mid\text{where (\ref{IP1}) is
feasible}\\}.$

It is easy to see that

$\displaystyle|A^{(1)}|<\ldots<|A^{(f)}|<|A^{(f+1)}|=n$

holds, where $f$ is the largest number such that $|A^{(f)}|<n$. Each target
value in the interval $I^{(f+1)}$ is feasible, which implies that each target
value in $|A^{(k)}|$ for $k>f$ has to be feasible as well.

In the following lemma we state a central property of the feasibility sets
$A^{(i)}$ that will be essential in the following algorithm as it allows to
compute feasibility sets from other feasibility sets with smaller indices. A
similar recursive argument was used in [22].

######  Lemma 2.

For every $i,j\geq 1$ the following equation holds:

$\displaystyle A^{(i+j)}=(A^{(i)}+A^{(j)}+S)\cap I^{(i+j)}$

###### Proof.

Let $t\in A^{(i+j)}$ be a feasible target value. By definition, there exists a
solution $x\in\mathbb{Z}^{n}$ such that
$\sum_{i=0}^{n}x_{i}a_{i}=t\leq(i+j)a_{n}$. There exist subvectors
$x^{\prime},x^{\prime\prime}\leq x$ such that
$x^{\prime}+x^{\prime\prime}+e_{k}=x$ for some unit vector $e_{k}$ and

$\displaystyle t^{\prime}:=\sum_{l=0}^{n}x^{\prime}_{l}a_{l}<$
$\displaystyle~{}ia_{n},$ $\displaystyle
t^{\prime\prime}:=\sum_{k=l}^{n}x^{\prime\prime}_{l}a_{l}<$
$\displaystyle~{}ja_{n},$ $\displaystyle t^{\prime}+t^{\prime\prime}+a_{k}=$
$\displaystyle~{}t,$

holds. Hence there exists a split of this sum into
$t^{\prime}+t^{\prime\prime}+a_{k}=t$ for some $a_{k}\in S$, $t^{\prime}\in
A^{(i)}$ and $t^{\prime\prime}\in A^{(j)}$. ∎

###  3.1 Solving Unbounded SubsetSum

Based on Lemma 2, we can now compute the feasible target values in the
relevant interval $I^{(k)}$, with $t\in I^{(k)}$ using a binary exponentiation
argument and therefore find a solution to Unbounded SubsetSum.

Algorithm 1 Solving Unbounded SubsetSum

  1. 1.

Use the algorithm of Bringmann [12] to compute $A^{(1)}$.

  2. 2.

Compute sets $A^{(2^{i})}$ iteratively by

$\displaystyle A^{(2^{i})}=\left(A^{(2^{i-1})}+A^{(2^{i-1})}+S\right)\cap
I^{(2^{i})}$

for all $i\leq R$, where $R$ is defined by the smallest index with
$|A^{(2^{R})}|=a_{n}$ or $2^{R}\geq k$. If $|A^{(2^{R})}|=a_{n}$ and
$2^{R}\leq k$ then return that $t$ is feasible.

  3. 3.

Starting with $A^{(1)}$, compute $A^{(k)}$ iteratively by

$\displaystyle{A^{(\ell+2^{i})}=(A^{(\ell)}+A^{(2^{i})}+S)\cap
I^{(\ell+2^{i})}}$

for every index $i\in Bin(k)$, where $Bin(k)$ is the set of indices with a $1$
in the binary encoding of $k$, i.e. $\sum_{i\in Bin(k)}2^{i}=k$.

  4. 4.

If $t\in A^{(k)}$ return that $t$ is feasible; otherwise return that $t$ is
not a feasible target value.

######  Theorem 5.

Unbounded SubsetSum can be solved in time

$\displaystyle O\Big{(}a_{n}\log
a_{n}\cdot\log\big{(}\min\\{\frac{t}{a_{n}};\frac{F}{a_{n}}\\}\big{)}\Big{)}=O(a_{n}\log
a_{n}\cdot\log(\frac{a_{n}}{n})).$

###### Proof.

Correctness
To show the correctness of Algorithm 1 one has to prove that the sets
$A^{(i)}$ are computed correctly, i.e. a target value $t\in I^{(j)}$ is
feasible if and only if $t\in A^{(j)}$.

The algorithm of Bringmann [12] that is used in step (1) computes all feasible
target values $t^{\prime}\leq t$ for a given $t$ in time $O(t\log t)$. By
setting $t=a_{n}$, we obtain the feasibility set $A^{(1)}$.

The correctness of the other feasibility sets $A^{(i)}$ for $i>1$ that are
computed in step (2) and (3) of the algorithm follows directly by Lemma 2.

Running Time
The running time of the algorithm depends on how many sumset computation are
performed. As each sumset is computed for intervals $I^{(i)}$ of the same
length $a_{n}$, the running time for each sumset computation is bounded by
$O(a_{n}\log a_{n})$.

In step (2) and (3) of the algorithm a total of $O(R)=O(\min\\{\log
k,\log\frac{F}{a_{n}}\\})=O(\min\\{\log\frac{t}{a_{n}},\log\frac{F}{a_{n}}\\})=O(\frac{F}{a_{n}})$
are being performed. Summing up, we obtain a running time of

$\displaystyle O\Big{(}a_{n}\log
a_{n}\cdot\log\big{(}\min\\{\frac{t}{a_{n}};\frac{F}{a_{n}}\\}\big{)}\Big{)}$

for the algorithm. Using that $F$ is bounded by $O(\frac{a_{n}^{2}}{n})$ [18],
we obtain a running time of $O(a_{n}\log a_{n}\cdot\log(\frac{a_{n}}{n}))$. ∎

###  3.2 Solving the Frobenius Problem

Having Algorithm 1 at hand, we can easily solve the Frobenius problem. We use
a binary search to determine the largest index $f$ with $|A^{(f)}|<n$ by
applying Algorithm 1 repeatedly to determine the sets $A^{(i)}$ and their
respective cardinality. Recall that $|A^{(1)}|\leq|A^{(2)}|\leq\ldots$ and
hence $|A^{(f+1)}|=n$ implies that all target values $t>fa_{n}$ are feasible.
Therefore, the largest infeasible target value (i.e. the Frobenius number) has
to be contained in $A^{(f)}$.

Algorithm 2 Solving Frobenius

  1. 1.

Compute the sets $A^{(2^{0})},A^{(2^{1})},\ldots,A^{(2^{R})}$ as in steps
(1)–(3) of Algorithm 1, where $R$ is the smallest number with
$|A^{(2^{R})}|=n$.

  2. 2.

Do a binary search in the interval $[2^{R-1},2^{R})$ to determine the largest
index $f\in[2^{R-1},2^{R})$ with $|A^{(f)}|<n$.

  3. 3.

Return the Frobenius number $F=f\cdot a_{n}+r$, where
$r=\max\big{\\{}(I^{(f)}\setminus A^{(f)})\big{\\}}$.

The naive approach of using Algorithm 1 to determine the sets $A^{(i)}$ leads
to a running time of $O(a_{n}\log^{3}a_{n})$ as the algorithm has to be called
at most $\log 2^{R-1}=O(\log a_{n})$ many times. Surprisingly, this running
time can be improved by computing the sets $A^{(i)}$ that are required in the
binary search in a more efficient way. The following algorithm computes $f$
without repeatedly using Algorithm 1 and instead relies on the precomputed
feasibility sets $A^{(2^{i})}$. This improves the running time of the
algorithm by a logarithmic factor.

Algorithm 3 Efficient Binary Search

$L:=2^{R-1}$ $\triangleright$ Set $L$ as the left index of the interval of the
binary search

for $i=R-2$ downto $0$ do

$A^{(L+2^{i})}=(A^{(L)}+A^{(2^{i})}+S)\cap I^{(L+2^{i})}$ $\triangleright$ The
middle element $L+2^{i}$ of the interval

if $|A^{(L+2^{i})}|<a_{n}$ then

$L:=L+2^{i}$

end if

end for

return $L$

Note that Algorithm 3 simulates a classical binary search with $L$ being the
leftmost index of the binary search interval and $L+2^{R-1-i}$ being the
rightmost index of the binary search interval after $i$ iterations. Depending
on the cardinality of the middle element $A^{(L+2^{R-2-i})}$ the binary search
continues in the left interval $[L,L+2^{R-2-i}]$ or in the right interval
$[L+2^{R-2-i},L+2^{R-1-i}]$.

Using this algorithm in step (2) of Algorithm 2 leads to the following
statement.

######  Theorem 6.

The Frobenius problem can be solved in time

$\displaystyle O(a_{n}\log a_{n}\cdot\log\frac{F}{a_{n}})=O(a_{n}\log
a_{n}\cdot\log\frac{a_{n}}{n}).$

###### Proof.

Correctness
The correctness of the algorithm follows directly from the fact that the
feasibility sets $A^{(i)}$ are computed correctly and that the binary search
computes the largest index $f$ with $|A^{(f)}|<n$.

Running time
In step (1) of the algorithm, the feasibility sets
$A^{(2^{0})},A^{(2^{1})},\ldots,A^{(2^{R})}$ are computed which requires a
running time of $O(a_{n}\log a_{n}\cdot\log(\frac{F}{a_{n}}))$ (see Theorem
5).

In the binary search in Algorithm 3, a total of $O(R)=O(\log\frac{F}{a_{n}})$
sumset computations are performed which requires a running time of
$O(a_{n}\log a_{n}\cdot\log\frac{F}{a_{n}})$.

Step (3) of the algorithm requires only $O(a_{n})$ time and hence the total
running time of the algorithm can be bounded by

$\displaystyle O(a_{n}\log a_{n}\cdot\log(\frac{F}{a_{n}})).$

∎

###  3.3 Solving AllTargets

The key ingredient to efficiently solving AllTargets is by a trade-off
argument of two algorithms. The algorithm of Böcker and Lipták [10] performs
well in the case that $n$ is small as it has a running time of $O(na_{0})$.
The other algorithm computes the feasibility sets $A^{(i)}$ stepwise for
$i\leq f$ (i.e. it computes all feasible target values $\leq F$). In the case
that $n$ is large, the number of items in $A^{(1)}$ is large to begin with and
we can use a bound on $F$ to bound the number of computed feasibility sets .

Algorithm 4 Solving AllTargets

  1. 1.

If $n<(a_{n}\log a_{n})^{1/2}$ use the algorithm [10] to compute AllTargets.
Otherwise proceed as follows:

  2. 2.

Use the algorithm of [12] to compute $A^{(1)}$.

  3. 3.

While $|A^{(i)}|<n$ do

     * •

Set $a[i]=\min\Big{\\{}\\{a[i]\\}\cup\\{a\in A^{(i)}\mid a\equiv i\bmod
a_{0}\\}\Big{\\}}$

     * •

Compute $A^{(i+1)}$ by

$\displaystyle A^{(i+1)}=(A^{(i)}+S)\cap I^{(i+1)}.$

     * •

Set $i:=i+1$.

  4. 4.

Return sequence $a$.

We obtain the following statement regarding the running time of Algorithm 4:

######  Theorem 7.

AllTargets can be solved in time

$\displaystyle O(a_{n}^{3/2}\log^{1/2}a_{n}).$

###### Proof.

Case: $n<(a_{n}\log a_{n})^{1/2}$
In this case the algorithm of Böcker and Lipták [10] is used with a running
time of

$\displaystyle O(na_{0})=O(a_{n}^{3/2}\log^{1/2}a_{n}).$

Case: $n\geq(a_{n}\log a_{n})^{1/2}$
In this case the sets $A^{(1)},\ldots,A^{(1)},A^{(f+1)}$ are computed with
$|A^{(f)}|<n$ and $|A^{(f+1)}|=n$, which requires a running time of $O(f\cdot
a_{n}\log a_{n})$. By definition we know that $F\in A^{(f)}$ and hence $f\leq
F/a_{n}$. Using the bound by Erdös and Graham [18] yields

$\displaystyle O(f\cdot a_{n}\log a_{n})=O(\frac{F}{a_{n}}\cdot a_{n}\log
a_{n})=O(\frac{a_{n}^{2}\log a_{n}}{n})=O(a_{n}^{3/2}\log^{1/2}a_{n}).$

∎

###  3.4 Hardness of Parameterization by $a_{n}$

In a recent result by Abboud et al. [1] it was shown that under the SETH there
exists no algorithm for bounded subset sum with a sublinear running time in
$t$. Even more, the theorem also excludes the existence of an algorithm with a
running time for example of the form $t^{1-\epsilon}\cdot 2^{\sqrt{n}}$. In
their reduction they are not making use of the upper bounds of the variables
which implies that the same hardness also holds for Unbounded SubsetSum. This
hardness statement for Unbounded SubsetSum was made precise in [22].

######  Theorem 8 ([1],[22]).

Assuming SETH, then for any $\epsilon>0$ there exists a $\delta>0$ such that
there exists no algorithm for Unbounded SubsetSum with a running time of

$\displaystyle O(t^{1-\epsilon}\cdot 2^{\delta n}).$

Note that we can in general assume $t\geq a_{n}$ as items with a size $>t$ can
be removed from the instance. This implies that the same hardness statement
can be made for the parameter $a_{n}$ instead of $t$, which shows that
Algorithm 1 is (apart from logarithmic factors) nearly optimal under the
assumption of the SETH. In the following, we will show that we can derive the
same hardness statement for Frobenius which shows that Algorithm 2 is nearly
optimal.

In a classical paper by Ramirez-Alfonsin [28] it was shown that the Frobenius
problem is NP-hard. The author gave a computational reduction from Unbounded
SubsetSum which showed that Unbounded SubsetSum can be solved for a given
target value $t$ by solving only at most four instances of Frobenius. In those
instances the following item sizes were used:

$\displaystyle\bar{a}_{i}=2a_{i}\qquad\qquad\text{ for }0\leq i\leq n$
$\displaystyle\bar{a}_{n+1}=2F(a_{1},\ldots,a_{n})+1$ (3)
$\displaystyle\bar{a}_{n+2}=F(\bar{a}_{0},\ldots\bar{a}_{n},\bar{a}_{n+1})-2t$

The central theorem that is being used in the reduction is the following:

######  Theorem 9 (Ramirez-Alfonsin [28]).

For given $t\in\mathbb{Z}_{\geq 0}$ with $t\leq F(a_{0},\ldots,a_{n})$ there
exists a solution of (1) if and only if

$\displaystyle
F(\bar{a}_{0},\ldots\bar{a}_{n},\bar{a}_{n+1},\bar{a}_{n+2})<F(\bar{a}_{0},\ldots\bar{a}_{n},\bar{a}_{n+1}).$

Based on the above theorem one can solve Unbounded SubsetSum by first
computing whether $t>F(a_{1},\ldots,a_{n})$, in which case $t$ is feasible and
in the case that $t\leq F(a_{1},\ldots,a_{n})$ the algorithm computes
$F(\bar{a}_{0},\ldots\bar{a}_{n},\bar{a}_{n+1},\bar{a}_{n+2})$ and
$F(\bar{a}_{0},\ldots\bar{a}_{n},\bar{a}_{n+1})$ in order to decide by Theorem
9 if $t$ is feasible.

The reason that we can not directly use this reduction in combination with
Theorem 8 is that the item sizes defined in (3.4) are potentially larger than
$a_{n}$ or $t$. This is because $F(a_{0},\ldots,a_{n})$ can only be bounded by
a quadratic term in $a_{n}$. In the following theorem we show how to avoid
this quadratic dependency. By adding only $O(\log t)$ many additional items we
can show that the Frobenius number of the new instance can be bounded by
$O(t\log t)$.

######  Theorem 10.

Assuming SETH, for any $\epsilon$ there exists a $\delta>0$ such that
Frobenius can not be solved in time

$\displaystyle O(a_{n}^{1-\epsilon}\cdot 2^{\delta n}).$

###### Proof.

Assume that there exists an algorithm $\mathcal{A}$ for Frobenius . Then we
can use it to develop an algorithm $\mathcal{B}$ for Unbounded SubsetSum
solving an instance $\mathcal{I}$ with given target value $t$ and item sizes
$a_{0},\ldots,a_{n}$. Without loss of generality, we thereby assume that all
item sizes are less than $t$, i.e. $a_{n}\leq t$. Define a new instance
$\mathcal{I}^{\prime}$ of Unbounded SubsetSum with additional item sizes

$\displaystyle a_{n+i}=Ra_{0}+(2^{i}\bmod a_{0})\qquad\text{ for }0\leq
i\leq\log a_{0},$

where $R\in\mathbb{Z}$ is the smallest value with $Ra_{0}>t$. The instance
$\mathcal{I}^{\prime}$ has $\log a_{0}\leq\log t$ additional items and each
item is bounded in size by $Ra_{0}+\log a_{0}\leq 2t+\log a_{0}\leq 3t$. Since
the newly defined item sizes exceed $t$, we know that $t$ is a feasible target
value for instance $\mathcal{I}$ if and only if $t$ is a feasible target value
for the instance $\mathcal{I}^{\prime}$.

Claim: The Frobenius number of instance $\mathcal{I}^{\prime}$ is bounded by

$\displaystyle F(a_{0},\ldots,a_{n^{\prime}})<O(t\log t).$

Consider a target value $t^{\prime}\in\mathbb{Z}$ with $t^{\prime}>3t\log t$.
We will see that $t^{\prime}$ can be written by a subset of the items
$a_{n+1},\ldots,a_{n^{\prime}}$ and multiples of the item $a_{0}$. Let
$t^{\prime\prime}\equiv t^{\prime}\bmod a_{0}$ and let $I$ be the set of
indices with a $1$ in the binary encoding of $t^{\prime\prime}$. Then
$t^{\prime\prime}\equiv t^{\prime}\equiv\sum_{i\in I}2^{i}\equiv\sum_{i\in
I}a_{t+i}\bmod a_{0}$. Since each $a_{t+i}\leq 3t$ we know that

$\displaystyle\sum_{i\in I}a_{t+i}\leq 3t\log t\leq t^{\prime}$

and hence

$\displaystyle t^{\prime}=Ka_{0}+\sum_{i\in I}a_{t+i}$

for some $K\in\mathbb{Z}_{\geq 0}$ which proves the claim.

Knowing that the Frobenius number of instances $\mathcal{I}^{\prime}$ is
bounded by $O(t\log t)$, we can use the reduction of [28] to show the SETH
based hardness for Frobenius. Algorithm 5 solves Unbounded SubsetSum by using
Frobenius as a subroutine.

Algorithm 5 Solving Unbounded SubsetSum [28]

  1. 1.

If $t>F(a_{1},\ldots,a_{n})$ return that $t$ is feasible.

  2. 2.

Compute item sizes $\bar{a}_{0},\ldots,\bar{a}_{n^{\prime}+2}$.

  3. 3.

Return that $t$ is feasible if

$\displaystyle
F(\bar{a}_{0},\ldots\bar{a}_{n^{\prime}},\bar{a}_{n^{\prime}+1},\bar{a}_{n^{\prime}+2})<F(\bar{a}_{0},\ldots\bar{a}_{n^{\prime}},\bar{a}_{n^{\prime}+1}).$

Otherwise return that $t$ is not feasible.

Since $F(a_{0},\ldots,a_{n^{\prime}})$ is bounded by $O(t\log t)$, by
definition of the item sizes in (3.4) the item sizes
$\bar{a}_{0},\ldots,\bar{a}_{n^{\prime}+2}$ are also bounded by $O(t\log t)$.
Note that according to [28] we have
$F(a_{0},\ldots,a_{n^{\prime}})=4F(\bar{a}_{0},\ldots,\bar{a}_{n^{\prime}+1})$.

By Theorem 8, we know that for an arbitrary $\epsilon>0$ there exists a
$\delta>0$ such that there is no algorithm with a running time
$O(t^{1-\epsilon}\cdot 2^{\delta n})$ for Unbounded SubsetSum. Here, we can
assume that $\delta<\epsilon$ as the non-existence of an algorithm with a
running time of $O(t^{1-\epsilon}\cdot 2^{\delta n})$ for $\delta\geq\epsilon$
excludes the existence of an algorithm with improved running time of
$O(t^{1-\epsilon}\cdot 2^{\epsilon n})$.

Assume now that there exists an algorithm with a running time of
$O(a_{n}^{1-2\epsilon}\cdot 2^{\delta n})$ for Frobenius. Then by the above
construction we know that there also exists an algorithm for Unbounded
SubsetSum with a running time of

$\displaystyle O((t\log t)^{1-2\epsilon}\cdot 2^{\delta(n+\log t)})$
$\displaystyle=O((t\log t)^{1-2\epsilon}\cdot t^{\delta}\cdot 2^{\delta n})$
$\displaystyle=O((t\log t)^{1-2\epsilon+\delta}\cdot 2^{\delta n})$
$\displaystyle\overset{\delta<\epsilon}{=}O(t^{1-\epsilon}\cdot 2^{\delta
n}).$

However, this contradicts the assumption that no such algorithms exists for
Unbounded SubsetSum. ∎

##  4 Conclusion

We prove nearly matching upper and lower bounds for Unbounded
SubsetSum,Frobenius and AllTargets parameterized by $a_{0}$ and $a_{n}$
respectively. The only major gap left in the open is regarding the complexity
of AllTargets parameterized by $a_{n}$. To us it seems that an algorithm
beating the running time of $O(a_{n}^{3/2})$ is possible but very
sophisticated techniques are required, like an improvement to MinConv for the
case that the entries of the sequence are bounded or sophisticated structural
properties to the solution space are needed. An algorithm with a running time
of $O(M^{1-\epsilon}a_{n})$ for MinConv with entries bounded by $M$ for
example would improve upon the complexity of AllTargets. A hardness result
showing that AllTargets can not be solved in linear time would also be very
interesting as this would imply that the complexity of a parameterization of
$a_{0}$ and $a_{n}$ of the considered problems would behave differently.

Furthermore, it would also be interesting to improve upon the logarithmic
factors for the algorithms parameterized by $a_{n}$ or to show that this is
not possible under certain hardness assumptions. Note that a running time of
$O(a_{n}\log a_{n})$ is already necessary to apply a single FFT to an interval
$I$ of length $a_{n}$.

## References

  * [1] A. Abboud, K. Bringmann, D. Hermelin, and D. Shabtay.  Seth-based lower bounds for subset sum and bicriteria path.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41–57. SIAM, 2019.
  * [2] J. L. R. Alfonsín.  The diophantine Frobenius problem, volume 30.  Oxford University Press on Demand, 2005.
  * [3] I. Aliev, G. Averkov, J. A. De Loera, and T. Oertel.  Optimizing sparsity over lattices and semigroups.  In International Conference on Integer Programming and Combinatorial Optimization, pages 40–51. Springer, 2020.
  * [4] I. Aliev, J. A. De Loera, T. Oertel, and C. O’Neill.  Sparse solutions of linear diophantine equations.  SIAM Journal on Applied Algebra and Geometry, 1(1):239–253, 2017\.
  * [5] I. Aliev, M. Henk, and A. Hinrichs.  Expected frobenius numbers.  Journal of Combinatorial Theory, Series A, 118(2):525–531, 2011\.
  * [6] I. M. Aliev and P. M. Gruber.  An optimal lower bound for the frobenius problem.  Journal of Number Theory, 123(1):71–79, 2007.
  * [7] A. Backurs, P. Indyk, and L. Schmidt.  Better approximations for tree sparsity in nearly-linear time.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2215–2229. SIAM, 2017.
  * [8] D. Beihoffer, J. Hendry, A. Nijenhuis, and S. Wagon.  Faster algorithms for frobenius numbers.  the electronic journal of combinatorics, 12(1):R27, 2005.
  * [9] R. Bellman.  Dynamic programming.  Science, 153(3731):34–37, 1966.
  * [10] S. Bocker and Z. Lipták.  A fast and simple algorithm for the money changing problem.  Algorithmica, 48(4):413–432, 2007.
  * [11] A. Brauer and J. E. Shockley.  On a problem of frobenius.  Journal für die reine und angewandte Mathematik, 211:215–220, 1962.
  * [12] K. Bringmann.  A near-linear pseudopolynomial time algorithm for subset sum.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073–1084. SIAM, 2017.
  * [13] M. Bussieck, H. Hassler, G. J. Woeginger, and U. T. Zimmermann.  Fast algorithms for the maximum convolution problem.  Operations research letters, 15(3):133–141, 1994.
  * [14] M. Cygan, M. Mucha, K. Wegrzycki, and M. Wlodarczyk.  On problems equivalent to (min, +)-convolution.  ACM Trans. Algorithms, 15(1):14:1–14:25, 2019.
  * [15] D. Einstein, D. Lichtblau, A. Strzebonski, and S. Wagon.  Frobenius numbers by lattice point enumeration.  Integers, 7(1):A15, 2007.
  * [16] F. Eisenbrand and G. Shmonin.  Carathéodory bounds for integer cones.  Operations Research Letters, 34(5):564–568, 2006.
  * [17] F. Eisenbrand and R. Weismantel.  Proximity results and faster algorithms for integer programming using the Steinitz lemma.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 808–816. SIAM, 2018.
  * [18] P. Erdos and R. L. Graham.  On a linear diophantine problem of frobenius.  Acta Arith, 21(1):399–408, 1972.
  * [19] L. Fukshansky and S. Robins.  Frobenius problem and the covering radius of a lattice.  Discrete & Computational Geometry, 37(3):471–483, 2007.
  * [20] H. Greenberg.  Solution to a linear diophantine equation for nonnegative integers.  Journal of Algorithms, 9(3):343–353, 1988.
  * [21] R. Impagliazzo and R. Paturi.  On the complexity of k-sat.  Journal of Computer and System Sciences, 62(2):367–375, 2001.
  * [22] K. Jansen and L. Rohwedder.  On integer programming and convolution.  In A. Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [23] R. Kannan.  Lattice translates of a polytope and the frobenius problem.  Combinatorica, 12(2):161–177, 1992.
  * [24] K. Koiliaris and C. Xu.  Faster pseudopolynomial time algorithms for subset sum.  ACM Transactions on Algorithms (TALG), 15(3):1–20, 2019.
  * [25] M. Künnemann, R. Paturi, and S. Schneider.  On the fine-grained complexity of one-dimensional dynamic programming.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [26] G. S. Lueker.  Two NP-complete problems in nonnegative integer programming.  Princeton University. Department of Electrical Engineering, 1975.
  * [27] A. Nijenhuis.  A minimal-path algorithm for the “money changing problem”.  The American Mathematical Monthly, 86(10):832–835, 1979.
  * [28] J. L. Ramírez-Alfonsín.  Complexity of the frobenius problem.  Combinatorica, 16(1):143–147, 1996.
  * [29] B. H. Roune.  Solving thousand-digit frobenius problems using gröbner bases.  Journal of Symbolic Computation, 43(1):1–7, 2008.
  * [30] R. R. Williams.  Faster all-pairs shortest paths via circuit complexity.  SIAM Journal on Computing, 47(5):1965–1985, 2018.