Geodesic
The Frobenius Problem for Classes of Polynomial Solvability
Matematičeskie zametki, Tome 70 (2001) no. 6, pp. 845-853 
I. D. Kan. The Frobenius Problem for Classes of Polynomial Solvability. Matematičeskie zametki, Tome 70 (2001) no. 6, pp. 845-853. http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/
@article{MZM_2001_70_6_a3,
     author = {I. D. Kan},
     title = {The {Frobenius} {Problem} for {Classes} of {Polynomial} {Solvability}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {845--853},
     year = {2001},
     volume = {70},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/}
}
TY  - JOUR
AU  - I. D. Kan
TI  - The Frobenius Problem for Classes of Polynomial Solvability
JO  - Matematičeskie zametki
PY  - 2001
SP  - 845
EP  - 853
VL  - 70
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/
LA  - ru
ID  - MZM_2001_70_6_a3
ER  - 
%0 Journal Article
%A I. D. Kan
%T The Frobenius Problem for Classes of Polynomial Solvability
%J Matematičeskie zametki
%D 2001
%P 845-853
%V 70
%N 6
%U http://geodesic.mathdoc.fr/item/MZM_2001_70_6_a3/
%G ru
%F MZM_2001_70_6_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

The Frobenius problem is to find a method ($=$ algorithm) for calculating the largest “sum of money” that cannot be given by coins whose values $b_0,b_1,\dots,b_w$ are coprime integers. As admissible solutions (algorithms), it is common practice to study polynomial algorithms, which owe their name to the form of the dependence of time expenditure on the length of the original information. The difficulty of the Frobenius problem is apparent from the fact that already for $w=3$ the existence of a polynomial solution is still an open problem. In the present paper, we distinguish some classes of input data for which the problem can be solved polynomially; nevertheless, argumentation in the spirit of complexity theory of algorithms is kept to a minimum.

[1] Shevchenko V. N., Kachestvennye voprosy tselochislennogo programmirovaniya, Nauka, M., 1995 | Zbl

[2] Johnson S. M., “A linear diophantine problem”, Canad. J. Math., 12:2 (1960), 390–398 | MR | Zbl

[3] Rödset Ö. J., “On a linear diophantine problem of Frobenius, II”, J. Reine Angew. Math., 307/308 (1979), 431–440 | MR | Zbl

[4] Kan I. D., “Predstavlenie chisel lineinymi formami”, Matem. zametki, 68:2 (2000), 210–216 | MR | Zbl

[5] Kan I. D., “K probleme Frobeniusa”, Fundamentalnaya i prikladnaya matematika, 3:3 (1997), 821–835 | MR | Zbl

[6] Brauer A., Shockly J. E., “On a problem of Frobenius”, J. Reine Angew. Math., 211:3/4 (1962), 215–220 | MR | Zbl

[7] Lenstra H. W., “Integer programming with a fixed number of variables”, Math. of Oper. Res., 8:4 (1983), 538–548 | DOI | MR | Zbl

[8] Kai-Man Tsang, “On a linear diophantine problem of Frobenius”, Studia Scientarum Math. Hungarica, 23 (1988), 443–452 | MR

[9] Selmer E. S., “On the linear diophantine problem of Frobenius”, J. Reine Angew. Math., 293/294 (1977), 1–17 | MR | Zbl