|
This article is cited in 1 scientific paper (total in 1 paper)
The Frobenius Problem for Classes of Polynomial Solvability
I. D. Kan M. V. Lomonosov Moscow State University
Abstract:
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.
Received: 20.03.2000 Revised: 25.12.2000
Citation:
I. D. Kan, “The Frobenius Problem for Classes of Polynomial Solvability”, Mat. Zametki, 70:6 (2001), 845–853; Math. Notes, 70:6 (2001), 771–778
Linking options:
https://www.mathnet.ru/eng/mzm797https://doi.org/10.4213/mzm797 https://www.mathnet.ru/eng/mzm/v70/i6/p845
|
Statistics & downloads: |
Abstract page: | 473 | Full-text PDF : | 246 | References: | 60 | First page: | 1 |
|