From: tchow@lsa.umich.edu (Timothy Chow)
Subject: Re: Generalized Postage Stamp Problem
Date: Thu, 29 Apr 1999 14:23:37 GMT
Newsgroups: sci.math,sci.math.research
Keywords: Frobenius problem -largest total not expressible with n denominations

In article <37279142.147945@news.gte.net>,
Eliot Jacobson <teliot@gte.net> wrote:
>I have a very bright student who is working on the general solution to
>the postage stamp problem, that is, finding a closed form solution for
>3 or more stamps.

This has been solved.

>I have looked around at the Internet and there isn't much there to
>help us on this problem.

The Internet still cannot begin to compete with a good library when it comes
to looking up mathematical facts (unless MathSciNet counts as part of the
Internet even though it's not free).  However, this case is an exception.
See http://www.cs.cmu.edu/~kannan/Papers/pubs.html and look for papers on
the Frobenius problem.
-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
Where a calculator like the ENIAC today is equipped with 18,000 vacuum tubes
and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes
and perhaps weigh only 1 1/2 tons.   ---Popular Mechanics, March 1949, p.258
==============================================================================

From: gwoegi@fmatbds01.tu-graz.ac.REMOVE.at (Gerhard J. Woeginger)
Subject: Re: Generalized Postage Stamp Problem
Date: Thu, 29 Apr 1999 19:35:56
Newsgroups: sci.math.research

In article <37279142.147945@news.gte.net> teliot@gte.net (Eliot Jacobson) writes:
>From: teliot@gte.net (Eliot Jacobson)
>Subject: Generalized Postage Stamp Problem
>Date: Wed, 28 Apr 1999 23:02:02 GMT

>Recall that the postage stamp problem states that if two stamp values
>A and B are relatively prime, then all sufficiently large postages can
>be made.  In fact, sufficiently large is (A - 1)*(B - 1).

>I have a very bright student who is working on the general solution to
>the postage stamp problem, that is, finding a closed form solution for
>3 or more stamps.  He has made come progress, having obtained some
>delightful closed forms for certain specialized cases.  Today he told
>me that the solution of the problem with 3 stamps is equivalent to a
>single integer solution to a certain polynomial in 8 variables.

>I have looked around at the Internet and there isn't much there to
>help us on this problem.

This problem is often called "Frobenius problem".  Ravi Kannan has given a 
polynomial time algorithm for the case that the number of stamp values is 
constant and not part of the input.  The general problem (where the number of 
stamp values *is* part of the input)  is NP-hard; the proof appeared in 
"Combinatorica" a few years ago, and it had "Frobenius" in the title of the 
paper.

Gerhard
___________________________________________________________
Gerhard J. Woeginger  (gwoegi@opt.math.tu-graz.ac.at)