On tropical knapsack-type problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909023935135744 |
|---|---|
| author | Buchinskiy, I. M. Kotov, M. V. Treier, A. V. |
| author_facet | Buchinskiy, I. M. Kotov, M. V. Treier, A. V. |
| contents | 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 \times k$ with non-negative entries over the max-plus algebra and the semigroup square matrices of size $k \times k$ with positive entries over the max-times algebra. We prove that the knapsack problem and subset sum problem for these structures are $\textsf{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_09983 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On tropical knapsack-type problems Buchinskiy, I. M. Kotov, M. V. Treier, A. V. Combinatorics 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 \times k$ with non-negative entries over the max-plus algebra and the semigroup square matrices of size $k \times k$ with positive entries over the max-times algebra. We prove that the knapsack problem and subset sum problem for these structures are $\textsf{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. |
| title | On tropical knapsack-type problems |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.09983 |