We study the time complexity of computing the $(\min,+)$ matrix product of two $n\times n$ integer matrices in terms of $n$ and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most $m_1$ monotone subsequences and each column of the second matrix can be decomposed into at most $m_2$ monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the $(\min,+)$ product of the matrices can be computed in $O(m_1m_2n^{2.569})$ time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or {\em vice versa} then this case is as hard as the general one. Similarly, we also study the time complexity of computing the $(\min,+)$ convolution of two $n$-dimensional integer vectors in terms of $n$ and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most $m_1$ monotone subsequences and the second vector can be decomposed into at most $m_2$ subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or {\em vice versa} then their $(\min,+)$ convolution can be computed in $\tilde{O}(m_1m_2n^{1.5})$ time. On the other, the case when both vectors are non-decreasing or both of them are non-increasing is as hard as the general case.


翻译:暂无翻译

0
下载
关闭预览

相关内容

专知会员服务
32+阅读 · 2021年3月7日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
ExBert — 可视化分析Transformer学到的表示
专知会员服务
31+阅读 · 2019年10月16日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
【NeurIPS2019】图变换网络:Graph Transformer Network
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
可解释AI(XAI)工具集—DrWhy
专知
25+阅读 · 2019年6月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
Arxiv
0+阅读 · 2023年10月20日
VIP会员
相关VIP内容
专知会员服务
32+阅读 · 2021年3月7日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
ExBert — 可视化分析Transformer学到的表示
专知会员服务
31+阅读 · 2019年10月16日
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
【NeurIPS2019】图变换网络:Graph Transformer Network
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
可解释AI(XAI)工具集—DrWhy
专知
25+阅读 · 2019年6月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
3+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员