会员服务
极小点 · 成对型 · 离散数学 · 社会计算 ·
2022 年 11 月 22 日
A min-max theorem for the minimum fleet-size problem
翻译：最小舰队规模问题最低度定理
Tinghan Ye,David Shmoys
Tinghan Ye,David Shmoys

A retrospective fleet-sizing problem can be solved via bipartite matching, where a maximum cardinality matching corresponds to the minimum number of vehicles needed to cover all trips. We prove a min-max theorem on this minimum fleet-size problem: the maximum number of pairwise incompatible trips is equal to the minimum fleet size needed.


翻译：车队的回溯性问题可以通过双方配对来解决,在这种配对中,最大基点匹配与所有旅行所需的最低车辆数量相对应。 我们证明关于这一最低车队规模问题的最起码理论:双向不相容旅行的最大次数相当于所需的最低车队规模。
0
下载
关闭预览

相关内容

33页PPT【AI+天气预测】，AI and Machine learning for weather predictions
33页PPT【AI+天气预测】，AI and Machine learning for weather predictions
专知会员服务
31+阅读 · 2022年3月5日
【如何做研究】How to research ，22页ppt
【如何做研究】How to research ，22页ppt
专知会员服务
108+阅读 · 2021年4月17日
Linux导论，Introduction to Linux，96页ppt
Linux导论，Introduction to Linux，96页ppt
专知会员服务
78+阅读 · 2020年7月26日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
88+阅读 · 2020年2月12日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
47+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
34+阅读 · 2019年10月17日
Stabilizing Transformers for Reinforcement Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
176+阅读 · 2019年10月11日
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
专知会员服务
79+阅读 · 2019年10月10日
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
MicroRNA靶向调控OSTF1在氟中毒鱼鳃渗透调节中的作用机制
国家自然科学基金
0+阅读 · 2015年12月31日
雷帕霉素类新型mTOR变构抑制剂的发现及其构效关系研究
国家自然科学基金
0+阅读 · 2015年12月31日
抗MRSA活性rhodomyrtosone B类似物的合成和构效关系研究
国家自然科学基金
0+阅读 · 2015年12月31日
靶向代谢型谷氨酸受体8变构调节位点的3DShapeSim药物发现与镇痛作用研究
国家自然科学基金
0+阅读 · 2015年12月31日
Anderson型多酸的不对称修饰及可控组装研究
国家自然科学基金
1+阅读 · 2014年12月31日
M2L2型水溶性金属-药物配合物的定向合成与抗肿瘤活性研究
国家自然科学基金
0+阅读 · 2013年12月31日
金融与管理中的HJB方程组的高效有限元方法
国家自然科学基金
0+阅读 · 2013年12月31日
高灵敏度恒温扩增检测端粒酶活性及端粒酶抑制剂的筛选
国家自然科学基金
0+阅读 · 2013年12月31日
Witten Laplacian的特征值及与其相关的Ricci Soliton研究
国家自然科学基金
0+阅读 · 2012年12月31日
复合污染条件下DOM对典型离子性抗生素吸附迁移行为的影响
国家自然科学基金
0+阅读 · 2008年12月31日
LEGO-Net: Learning Regular Rearrangements of Objects in Rooms
Arxiv
0+阅读 · 2023年1月23日
Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics
Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics
Arxiv
0+阅读 · 2023年1月23日
The Simultaneous Assignment Problem
Arxiv
0+阅读 · 2023年1月21日
On the power of foundation models
Arxiv
0+阅读 · 2023年1月21日
Convergent approaches for the Dirichlet Monge ampère problem
Convergent approaches for the Dirichlet Monge ampère problem
Arxiv
0+阅读 · 2023年1月20日
Stable Probability Weighting: Large-Sample and Finite-Sample Estimation and Inference Methods for Heterogeneous Causal Effects of Multivalued Treatments Under Limited Overlap
Arxiv
0+阅读 · 2023年1月19日
On the Vulnerability of Backdoor Defenses for Federated Learning
On the Vulnerability of Backdoor Defenses for Federated Learning
Arxiv
0+阅读 · 2023年1月19日
A $J$-Symmetric Quasi-Newton Method for Minimax Problems
Arxiv
0+阅读 · 2023年1月19日
General Greedy De-bias Learning
Arxiv
0+阅读 · 2023年1月19日
Emergent Bartering Behaviour in Multi-Agent Reinforcement Learning
Emergent Bartering Behaviour in Multi-Agent Reinforcement Learning
Arxiv
19+阅读 · 2022年5月13日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
极小点
成对型
离散数学
社会计算
相关VIP内容
33页PPT【AI+天气预测】，AI and Machine learning for weather predictions
33页PPT【AI+天气预测】，AI and Machine learning for weather predictions
专知会员服务
31+阅读 · 2022年3月5日
【如何做研究】How to research ，22页ppt
【如何做研究】How to research ，22页ppt
专知会员服务
108+阅读 · 2021年4月17日
Linux导论，Introduction to Linux，96页ppt
Linux导论，Introduction to Linux，96页ppt
专知会员服务
78+阅读 · 2020年7月26日
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
图像分类技巧集，17页ppt《Bag of Tricks for Image Classification》
专知会员服务
94+阅读 · 2020年3月12日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
88+阅读 · 2020年2月12日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
47+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
34+阅读 · 2019年10月17日
Stabilizing Transformers for Reinforcement Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
59+阅读 · 2019年10月17日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
176+阅读 · 2019年10月11日
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
专知会员服务
79+阅读 · 2019年10月10日
热门VIP内容
相关资讯
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium3
中国图象图形学学会CSIG
0+阅读 · 2021年11月9日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
相关论文
LEGO-Net: Learning Regular Rearrangements of Objects in Rooms
Arxiv
0+阅读 · 2023年1月23日
Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics
Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics
Arxiv
0+阅读 · 2023年1月23日
The Simultaneous Assignment Problem
Arxiv
0+阅读 · 2023年1月21日
On the power of foundation models
Arxiv
0+阅读 · 2023年1月21日
Convergent approaches for the Dirichlet Monge ampère problem
Convergent approaches for the Dirichlet Monge ampère problem
Arxiv
0+阅读 · 2023年1月20日
Stable Probability Weighting: Large-Sample and Finite-Sample Estimation and Inference Methods for Heterogeneous Causal Effects of Multivalued Treatments Under Limited Overlap
Arxiv
0+阅读 · 2023年1月19日
On the Vulnerability of Backdoor Defenses for Federated Learning
On the Vulnerability of Backdoor Defenses for Federated Learning
Arxiv
0+阅读 · 2023年1月19日
A $J$-Symmetric Quasi-Newton Method for Minimax Problems
Arxiv
0+阅读 · 2023年1月19日
General Greedy De-bias Learning
Arxiv
0+阅读 · 2023年1月19日
Emergent Bartering Behaviour in Multi-Agent Reinforcement Learning
Emergent Bartering Behaviour in Multi-Agent Reinforcement Learning
Arxiv
19+阅读 · 2022年5月13日
相关基金
MicroRNA靶向调控OSTF1在氟中毒鱼鳃渗透调节中的作用机制
国家自然科学基金
0+阅读 · 2015年12月31日
雷帕霉素类新型mTOR变构抑制剂的发现及其构效关系研究
国家自然科学基金
0+阅读 · 2015年12月31日
抗MRSA活性rhodomyrtosone B类似物的合成和构效关系研究
国家自然科学基金
0+阅读 · 2015年12月31日
靶向代谢型谷氨酸受体8变构调节位点的3DShapeSim药物发现与镇痛作用研究
国家自然科学基金
0+阅读 · 2015年12月31日
Anderson型多酸的不对称修饰及可控组装研究
国家自然科学基金
1+阅读 · 2014年12月31日
M2L2型水溶性金属-药物配合物的定向合成与抗肿瘤活性研究
国家自然科学基金
0+阅读 · 2013年12月31日
金融与管理中的HJB方程组的高效有限元方法
国家自然科学基金
0+阅读 · 2013年12月31日
高灵敏度恒温扩增检测端粒酶活性及端粒酶抑制剂的筛选
国家自然科学基金
0+阅读 · 2013年12月31日
Witten Laplacian的特征值及与其相关的Ricci Soliton研究
国家自然科学基金
0+阅读 · 2012年12月31日
复合污染条件下DOM对典型离子性抗生素吸附迁移行为的影响
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员
Top