Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:3, 334-346
Volume 24, No 3, 2017, P. 104-124
UDC 519.6
V. M. Fomichev
Computational complexity of the original and extended Diophantine Frobenius problem
Abstract:
We deduce the law of nonstationary recursion which makes it possible, for given a primitive set$A = {a_1, . . . , a_k}$, $k > 2$, to construct an algorithm for finding the set of the numbers outside the additive semigroup generated by $A$. In particular, we obtain a new algorithm for determining the Frobenius numbers$g(a_1, . . . , a_k)$ . The computational complexity of these algorithms is estimated in terms of bit operations. We propose a two-stage reduction of the original primitive set to an equivalent primitive set that enables us to improve complexity estimates in the cases when the two-stage reduction leads to a substantial reduction of the order of the initial set.
Bibliogr. 16.
Keywords: Frobenius number, primitive set, additive semigroup, computational complexity.
DOI: 10.17377/daio.2017.24.537
Vladimir M. Fomichev 1,2
1. Financial University under the Government of the Russian Federation,
49 Leningradsky Ave., 125993 Moscow, Russia,
2. National Research Nuclear University MEPhI,
31 Kashirskoe Highway, 115409 Moscow, Russia
e-mail: fomichev@nm.ru
Received 8 April 2016
Revised 31 October 2016
References
[1] V. I. Arnold, Experimental observation of mathematical facts, MTsNMO, Moscow, 2006.[2] A. V. Ustinov, The solution of Arnold’s problem on the weak asymptotics of Frobenius numbers with three arguments, Mat. Sb., 200, No. 4, 131–160, 2009. Translated in Sb. Math., 200, No. 4, 597–627, 2009.
[3] A. V. Ustinov, Geometric proof of Rødseth’s formula for Frobenius numbers, Tr. Mat. Inst. Steklova, 276, 280–287, 2012. Translated in Proc. Steklov Inst. Math., 276, No. 1, 275–282, 2012.
[4] V. M. Fomichev, Primitive sets of numbers being equivalent by Frobenius, Prikladn. Diskretn. Mat., No. 1, 20–26, 2014.
[5] V. M. Fomichev, Estimates for exponent of some graphs by means of Frobenius’s numbers of three arguments, Prikladn. Diskretn. Mat., No. 2, 88–96, 2014.
[6] S. Böcker and Zs. Lipták, The Money Changing Problem revisited: Computing the Frobenius number in time $O(ka_1)$, in Computing and Combinatorics (Proc. 4th Annu. Int. Conf., Kunming, China, Aug. 16–19, 2005), pp. 965–974, Springer, Heidelberg, 2005 (Lect. Notes Comput. Sci., Vol. 3595).
[7] C. Bogart, Calculating Frobenius numbers with Boolean Toeplitz matrix multiplication, 2009. Available at http://quetzal.bogarthome.net/frobenius.pdf (accessed Mar. 10, 2017).
[8] A. Brauer, On a problem of partitions, Am. J. Math., 64, 299–312, 1942.
[9] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math., 211, 215–220, 1962.
[10] F. Curtis, On formulas for the Frobenius number of a numerical semigroup, Math. Scand., 67, 190–192, 1990.
[11] B. R. Heap and M. S. Lynn, A graph-theoretic algorithm for the solution of a linear Diophantine problem of Frobenius, Numer. Math., 6, 346–354, 1964.
[12] B. R. Heap and M. S. Lynn, On a linear Diophantine problem of Frobenius: An improved algorithm, Numer. Math., 7, 226–231, 1965.
[13] D. B. Johnson, Efficient algorithms for shortest paths in space networks, J. ACM, 24, 1–13, 1977.
[14] M. Nijenhuis, A minimal-path algorithm for the “Money changing problem”, Am. Math. Mon., 86, 832–835, 1979.
[15] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Clarendon Press, Oxford, 2005 (Oxf. Lect. Ser. Math. Appl., Vol. 30).
[16] J. J. Sylvester, Problem 7382, in Mathematical Questions with Their Solutions: From the “Educational Times”, Vol. 41, p. 21, Francis Hodgson, London, 1884. Available at http://archive.org/stream/mathematicalque05unkngoog#page/n150/mode/2up. Accessed Mar. 10, 2017.
