On tropical knapsack-type problems
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 [Formula: see text] with non-negative entries over the max-plus algebra and the semigroup of square matrices of size [Formula: see text] with positive entries over the max-times algebra. We prove that the knapsack problem and the subset sum problem for these structures are [Formula: see text]-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.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Optimization Algorithms Research
Advanced Graph Theory Research
Publication details
- Journal / source
- International Journal of Algebra and Computation
- Publisher
- World Scientific Pub Co Pte Ltd
- Volume
- 36
- Issue
- 07
- Pages
- 721–741
- Publication date
- 30 March 2026
- Language
- EN