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 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)