 |
|
|
|
|
 |
 |
|
Frobenius Numbers by Toric Gröbner Bases
|
|
|
|
|
|
| Organization: | Wolfram Research, Inc. |
|
|
|
|
|
|
ACA 2005
|
|
|
|
|
|
Nara Women's University, Nara, Japan
|
|
|
|
|
|
A talk from the Conference on Applications of Computer Algebra (ACA) 2005 on a method of computing of Frobenius numbers that uses Gröbner bases.
Abstract:
Given a set A = {a1...an} of positive integers with gcd 1, it is not hard to show that all "sufficiently large" integers can be represented as a nonnegative integer combination of elements of A. The Frobenius number of the set is defined as the largest integer not so representable. The Frobenius instance problem (also called the money changing or postage stamp problem) is to determine, given a positive integer M, a set of nonnegative integers X={x1...xn} such that X.A=n, or else show no such set exists. We will briefly recall how this can be addressed via toric Gröbner bases.
It is known that the Frobenius number problem is NP-hard in general. For dimension 2 it is trivial (Sylvester solved in two decades before Frobenius publicized the problem). In dimension 3 a very efficient method was found independently by Greenberg and Davison. For higher dimensions some quite effective methods are known for the case where one element of A is not too large (say, less than 107).
Recent work has given rise to methods that are effective when the above restrictions do not hold, although the dimension must be bounded by 10 or so. It turns out that there is a way to recast this work using toric Gröbner bases, wherein the "fundamental domain" for the set A is given by the staircase of the basis with respect to a particular ordering. It is reasonably efficient in dimensions 4 to 7, when the elements in the set are as large as 1040 or so. We will illustrate this.
|
|
|
|
|
|
|
|
|
|
|
|
Frobenius numbers, Toric Gröbner Bases
|
|
|
|
|
|
http://www.jssac.org/Conference/ACA
|
|
|
 |
|
|
| ACA2005_Frobenius.pdf (96.9 KB) - PDF Document | | ACA2005_Frobenius.nb (326.9 KB) - Mathematica Notebook |
|
|
For the newest resources, visit Wolfram Repositories and Archives »
