On tropical knapsack-type problems Full article
| Journal |
International Journal of Algebra and Computation
ISSN: 0218-1967 , E-ISSN: 1793-6500 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2026, DOI: 10.1142/S021819672650027X | ||||
| Tags | Max-plus algebra, max-times algebra, knapsack problem, subset sum problem, generic complexity | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Министерство науки и высшего образования РФ | FWNF-2026-0033 |
Abstract:
In this paper, we investigate the computational complexity of the knapsack problem and subset sum problem for the following tropical algebraic structures. We consider the semigroup of square matrices of size k×k with non-negative entries over the max-plus algebra and the semigroup of square matrices of size k×k with positive entries over the max-times algebra. We prove that the knapsack problem and the subset sum problem for these structures are NP-complete. We demonstrate that there are pseudo-polynomial algorithms to solve these problems. Also, we show that for the latter semigroup, there are polynomial generic algorithms to solve the knapsack problem and the subset sum problem.
This research was supported in accordance with the state task of the IM SB RAS,
project FWNF-2026-0033.
Cite:
Buchinskiy I.M.
, Kotov M.V.
, Treier A.V.
On tropical knapsack-type problems
International Journal of Algebra and Computation. 2026. DOI: 10.1142/S021819672650027X
On tropical knapsack-type problems
International Journal of Algebra and Computation. 2026. DOI: 10.1142/S021819672650027X
Dates:
| Submitted: | Mar 22, 2025 |
| Accepted: | Mar 2, 2026 |
| Published online: | Apr 21, 2026 |
Identifiers:
No identifiers