Geodesic
Generic polynomial algorithms for the knapsack problem in some matrix semigroups
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 100-109.

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

In this paper, we propose generic polynomial algorithms for the knapsack problems over semigroups of non-negative integer matrices of arbitrary order and semigroup of non-negative second-order integer matrices with determinant 1.
Keywords: generic complexity, knapsack problems
Mots-clés : integer matrices. 
@article{SEMR_2023_20_1_a2,
     author = {A. N. Rybalov},
     title = {Generic polynomial algorithms for the knapsack problem in some matrix semigroups},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {100--109},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a2/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generic polynomial algorithms for the knapsack problem in some matrix semigroups
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2023
SP  - 100
EP  - 109
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a2/
LA  - ru
ID  - SEMR_2023_20_1_a2
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generic polynomial algorithms for the knapsack problem in some matrix semigroups
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2023
%P 100-109
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a2/
%G ru
%F SEMR_2023_20_1_a2
A. N. Rybalov. Generic polynomial algorithms for the knapsack problem in some matrix semigroups. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 1, pp. 100-109. http://geodesic.mathdoc.fr/item/SEMR_2023_20_1_a2/

[1] S. Birmpilis, G. Labahn, A. Storjohann, “A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix”, J. Symb. Comput., 116 (2023), 146–182 | DOI | MR | Zbl

[2] V. Cacchiani, M. Iori, A. Locatelli, S. Martello, “Knapsack problems – an overview of recent advances. I: Single knapsack problems”, Comput. Oper. Res., 143 (2022), 105692 | DOI | MR | Zbl

[3] V. Cacchiani, M. Iori, A. Locatelli, S. Martello, “Knapsack problems - an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems”, Comput. Oper. Res., 143 (2022), 105693 | DOI | MR | Zbl

[4] M. Garey, D. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman and Company, San Francisco, 1979 | MR | Zbl

[5] D. Hirschfeldt, “Some questions in computable mathematics”, Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday, eds. Day Adam et al., Springer, Cham, 2017, 22–55 | DOI | MR | Zbl

[6] C. Jockusch, P. Schupp, “Generic computability, Turing degrees, and asymptotic density”, J. Lond. Math. Soc., II. Ser., 85:2 (2012), 472–490 | DOI | MR | Zbl

[7] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Generic-case complexity, decision problems in group theory, and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[8] R. Karp, “Reducibility among combinatorial problems”, Complexity of Computer Computations, Plenum Press, New York, 1973, 85–103 | MR | Zbl

[9] E. Karstadt, O. Schwartz, “Matrix multiplication, a little faster”, J. ACM, 67:1 (2020), 1 | DOI | MR | Zbl

[10] A. Miasnikov, A. Nikolaev, A. Ushakov, “Knapsack problems in groups”, Math. Comput., 84:292 (2015), 987–1016 | DOI | MR | Zbl

[11] V. Neiger, C. Pernet, “Deterministic computation of the characteristic polynomial in the time of matrix multiplication”, J. Complexity, 67 (2021), 101572 | DOI | MR | Zbl

[12] J. Nielsen, “Die Gruppe der dreidimensionalen Gittertransformationen”, Kgl. Danske Vid. Selsk., Math.-fys. Medd., 5:12 (1924), 3–29 | Zbl

[13] A. Rosowski, “Fast commutative matrix algorithms”, J. Symb. Comput., 114 (2023), 302–321 | DOI | MR | Zbl

[14] A. Rybalov, “On generic complexity of the subset sum problem for semigroups of integer matrices”, Prikl. Diskretn. Mat., 50 (2020), 118–126 | MR | Zbl

[15] A. Rybalov, “O genericheskoi slozhnosti problemy o summe podmnozhestv v monoidakh i gruppakh tselochislennykh matrits vtorogo poryadka”, Vestnik Omskogo universiteta, 25:4 (2020), 10–15

[16] S.M. Shperling, Y.A. Kochetov, “A knapsack problem for rectangles under center-of-gravity constraints”, J. Appl. Ind. Math., 16:3 (2022), 563–571 | DOI | MR

[17] V. Strassen, “Gaussian elimination is not optimal”, Numer. Math., 13:4 (1969), 354–356 | DOI | MR | Zbl

[18] S. Winograd, “On multiplication of $2 \times 2$ matrices”, Linear Algebra Appl., 4 (1971), 381–388 | DOI | MR | Zbl