|
|
|
|
|
|
 |
 |
|
Making Change and Finding Repfigits: Balancing a Knapsack
|
|
|
|
|
|
| Organization: | Wolfram Research, Inc. |
|
|
|
|
|
|
ICMS 2006
|
|
|
|
|
|
Castro Urdiales, Spain
|
|
|
|
|
|
This work was presented at ICMS, Castro Urdiales, Spain, September 2, 2006. The article is a longer version, containing a code appendix. As there have been some code refinements since then, I include the better Mathematica code and tests in a file KeithNumbers.nb
Abstract:
We will discuss knapsack problems that arise in certain computational number theory settings. A common theme is that the search space for the standard real relaxation is large; in a sense this translates to a poor choice of variables. Lattice reduction methods have been developed in the past few years to improve handling of such problems. We show explicitly how they may be applied to computation of Frobenius instances, Keith numbers (also called "repfigits"), and as a first step in computation of Frobenius numbers.
|
|
|
|
|
|
|
|
|
|
|
|
integer linear programming, knapsack problems, Keith numbers, Frobenius instance solving, postage-stamp problem, change-making problem, lattice reduction
|
|
|
|
|
|
http://www.icms2006.unican.es
|
|
|
 |
|
|
| ICMS2006_lattice_ilp_talk.pdf (95.3 KB) - PDF Document | | lattice_ilp.pdf (94.7 KB) - PDF Document | | ICMS2006_lattice_ilp_talk.nb (342 KB) - Mathematica Notebook | | KeithNumbers.nb (236.5 KB) - Mathematica Notebook | | lattice_ilp.nb (252 KB) - Mathematica Notebook |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
