\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
\nopagenumbers
\noindent
%
%
{\bf Dale Beihoffer, Jemimah Hendry, Albert Nijenhuis and Stan Wagon}
%
%
\medskip
\noindent
%
%
{\bf Faster Algorithms for Frobenius Numbers}
%
%
\vskip 5mm
\noindent
%
%
%
%
The Frobenius problem, also known as the postage-stamp problem or the
money-changing problem, is an integer programming problem that seeks
nonnegative integer solutions to $ x_1 a_1 +\cdots + x_n
a_n =M$, where $ a_i $ and $M$ are positive integers. In particular,
the {\it Frobenius number} $f(A)$, where $A=\{ a_i \}$, is the
largest $M$ so that this equation fails to have a solution. A simple
way to compute this number is to transform the problem to a
shortest-path problem in a directed weighted graph; then Dijkstra's
algorithm can be used. We show how one can use the additional symmetry
properties of the graph in question to design algorithms that are very
fast. For example, on a standard desktop computer, our methods can
handle cases where $n=10$ and $ a_1 = 10^7$. We have two main new
methods, one based on breadth-first search and another that uses the
number theory and combinatorial structure inherent in the problem to
speed up the Dijkstra approach. For both methods we conjecture that
the average-case complexity is $O( a_1 \sqrt{n} )$. The previous best
method is due to B\"{o}cker and Lipt\'{a}k and runs in time $O( a_1
n)$. These algorithms can also be used to solve auxiliary problems
such as (1)~find a solution to the main equation for a given value of
$M$; or (2)~eliminate all redundant entries from a basis. We then show
how the graph theory model leads to a new upper bound on $f(A)$ that
is significantly lower than existing upper bounds. We also present a
conjecture, supported by many computations, that the expected value of
$f(A)$ is a small constant multiple of $ \left({1\over2} \, n! \,
\Pi A\right)^{1/(n-1)} -\Sigma A$.

\bye

.
