On the Frobenius Coin-Exchange Problem
Suppose you have an infinite supply of coins of N different relatively prime denominations, a1, a2, … aN. It is not difficult to show that there exists the maximum amount of change F = F(a1, a2, … aN) which CANNOT be given with these coins, and any amount larger than F can be given. The Frobenius problem (FP) asks for an algorithm that on the input would take N, a1, a2, … aN, and on the output return F. FP is known to be NP-complete, which in particular means that there can be no general formula for F, although a very simple such formula exists for N = 2 (this goes back to J. Sylvester, 1884). On the other hand, for each fixed N, FP is known to be in the P complexity class. There is a variety of upper and lower bounds for F in the literature, and recently some work has been done on trying to understand the behavior of F “on the average.” I will present an introduction to this exciting problem, which is extensively studied in number theory, complexity theory, combinatorics, and probability, and explores the interplay between these areas.
© 2009 Lenny Fukshansky
Fukshansky, Lenny. "On the Frobenius Coin-Exchange Problem." Graduate Seminar, California State University Channel Islands, Camarillo, California. 30 September 2009.