Faster algorithms for Frobenius numbers (Q2571269)

The Frobenius number of a set of positive integers \(A= \{a_1, \dots, a_n\}\) is the largest integer \(M\) such that the equation \(x_1 a_1 + \cdots + x_n a_n = M\) does not have a nonnegative integer solution. This paper gives two new algorithms for the (weak NP-hard) problem to compute the Frobenius number for a given set of integers. The first algorithm is based upon breadth first search; the second algorithm uses number theory and combinatorial insights in the problem to speed up a more straightforward algorithm based on Dijkstra's shortest paths algorithm. The algorithms can also be used to solve related problems. The authors give a method to obtain upper bounds for the Frobenius number.