.png){kind=icon}
返回
On tropical knapsack-type problems
.png){kind=icon}
PRE
AI
DOI：10.1142/s021819672650027x.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文研究了以下热带代数结构下的背包问题和子集和问题的计算复杂性。我们考虑了在max-plus代数上具有非负元素的大小为k×k的方阵半群，以及在max-times代数上具有正元素的大小为k×k的方阵半群。我们证明了这些结构下的背包问题和子集和问题是NP完全的。我们证明了存在伪多项式算法来求解这些问题。此外，我们还证明了对于后一种半群，存在多项式通用算法来求解背包问题和子集和问题。
Keyword:
Max-plus algebra
max-times algebra
knapsack problem
subset sum problem
generic complexity
期刊
I
IF:
0.5
论文数:
43
被引数:
0
机构
引用论文
暂无论文信息