数学 > 组合数学
[提交于 2012年5月31日
(此版本)
, 最新版本 2013年7月25日 (v2)
]
标题: 热带矩阵分解的复杂性
标题: The complexity of tropical matrix factorization
摘要: 热带算术运算在$\mathbb{R}$上由$a\oplus b=\min\{a,b\}$和$a\otimes b=a+b$定义。 设$A$为一个热带矩阵,$k$为一个正整数,热带矩阵分解(TMF)的问题是询问是否存在满足$B\otimes C=A$的热带矩阵$B\in\mathbb{R}^{m\times k}$和$C\in\mathbb{R}^{k\times n}$。我们证明对于每个固定的$k$,TMF 没有算法可能在多项式时间内工作,从而解决了 Barvinok 在 1993 年提出的问题。还表明 TMF 对于具有有界热带秩的矩阵也是困难的。证明如果$k\leq3$,TMF 可以由多项式时间算法解决,我们回答了 Develin、Santos 和 Sturmfels 提出的问题。 他们提出另一个问题,询问是否每个因子秩为$k$的热带矩阵都具有大小不超过$N(k)\times N(k)$的秩为$k$的子矩阵;我们对每个$k>4$都否定了这个问题。
文献和引用工具
与本文相关的代码,数据和媒体
alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)
演示
推荐器和搜索工具
arXivLabs:与社区合作伙伴的实验项目
arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.