会员服务
CASE · 约束 · 离散数学 ·
2021 年 10 月 5 日
Complexity of Traveling Tournament Problem with Trip Length More Than Three
翻译：旅行旅行旅行旅行旅行旅行旅行旅行旅行旅行旅行超过三三长的复杂程度问题
Diptendu Chatterjee
Diptendu Chatterjee
from arxiv, 11 pages, 2 figures

The Traveling Tournament Problem is a sports-scheduling problem where the goal is to minimize the total travel distance of teams playing a double round-robin tournament. The constraint 'k' is an imposed upper bound on the number of consecutive home or away matches. It is known that TTP is NP-Hard for k=3 as well as k=infinity. In this work, the general case has been settled by proving that TTP-k is NP-Complete for any fixed k>3.


翻译：旅行锦标赛是一个体育安排问题,目标是最大限度地减少参加双轮双轮赛的球队的总旅行距离。限制“k”是连续在家或离家比赛次数的上限。众所周知,TTP是k=3和k=finity的NP-hard。在这项工作中,通过证明TTP-k是固定K>3的NP-Complee,一般案例得到解决。
0
下载
关闭预览

相关内容

【干货书】开放数据结构，Open Data Structures，337页pdf
【干货书】开放数据结构，Open Data Structures，337页pdf
专知会员服务
16+阅读 · 2021年9月17日
【ICML2021】低秩Sinkhorn 分解
专知会员服务
38+阅读 · 2021年8月20日
2020数据工程师成长路线图
专知会员服务
17+阅读 · 2020年9月6日
【东京大学】图采样，Sampling on Graphs: From Theory to Applications
【东京大学】图采样，Sampling on Graphs: From Theory to Applications
专知会员服务
18+阅读 · 2020年3月10日
【跨语言BERT模型大集合】Transfer learning is increasingly going multilingual with language-specific BERT models
专知会员服务
53+阅读 · 2020年1月30日
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
9+阅读 · 2019年10月24日
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日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础，669页pdf
【新书】Python编程基础，669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
专知会员服务
79+阅读 · 2019年10月10日
Ray RLlib: Scalable 降龙十八掌
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
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日
【论文推荐】最新七篇强化学习相关论文—逻辑约束、综述、多任务深度强化学习、参数服务器、事件抽取、分层强化学习、过拟合研究
【论文推荐】最新七篇强化学习相关论文—逻辑约束、综述、多任务深度强化学习、参数服务器、事件抽取、分层强化学习、过拟合研究
专知
25+阅读 · 2018年4月29日
已删除
已删除
将门创投
4+阅读 · 2018年1月19日
R文本分类之RTextTools
R文本分类之RTextTools
R语言中文社区
4+阅读 · 2018年1月17日
分布式TensorFlow入门指南
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Python/OpenCV实现增强现实
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
多高的AUC才算高？
多高的AUC才算高？
ResysChina
7+阅读 · 2016年12月7日
Servicing Timed Requests on a Line
Arxiv
0+阅读 · 2021年11月30日
Sublinear-time Reductions for Big Data Computing
Arxiv
0+阅读 · 2021年11月30日
Risk-Free Bidding in Complement-Free Combinatorial Auctions
Arxiv
0+阅读 · 2021年11月29日
Bilu-Linial stability, certified algorithms and the Independent Set problem
Arxiv
0+阅读 · 2021年11月29日
Time-optimal self-stabilizing leader election in population protocols
Arxiv
0+阅读 · 2021年11月29日
A Chronology of Set Cover Inapproximability Results
Arxiv
0+阅读 · 2021年11月28日
A note on Matching-Cut in $P_t$-free Graphs
Arxiv
0+阅读 · 2021年11月27日
An Optimal Algorithm for Finding Champions in Tournament Graphs
Arxiv
0+阅读 · 2021年11月26日
Approximate counting and NP search problems
Arxiv
0+阅读 · 2021年11月26日
The Search Problem in Mixture Models
Arxiv
3+阅读 · 2018年2月24日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
CASE
约束
离散数学
相关VIP内容
【干货书】开放数据结构，Open Data Structures，337页pdf
【干货书】开放数据结构，Open Data Structures，337页pdf
专知会员服务
16+阅读 · 2021年9月17日
【ICML2021】低秩Sinkhorn 分解
专知会员服务
38+阅读 · 2021年8月20日
2020数据工程师成长路线图
专知会员服务
17+阅读 · 2020年9月6日
【东京大学】图采样，Sampling on Graphs: From Theory to Applications
【东京大学】图采样，Sampling on Graphs: From Theory to Applications
专知会员服务
18+阅读 · 2020年3月10日
【跨语言BERT模型大集合】Transfer learning is increasingly going multilingual with language-specific BERT models
专知会员服务
53+阅读 · 2020年1月30日
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
Risk Sensitive Portfolio Optimization with Regime-Switching and Default Contagion，香港理工大学应用数学系余翔助理教授，第八届全国社会媒体处理大会SMP2019
专知会员服务
9+阅读 · 2019年10月24日
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日
强化学习最新教程，17页pdf
强化学习最新教程，17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础，669页pdf
【新书】Python编程基础，669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
【人工智能在2019：一年回顾】反人工智能，AI in 2019: A Year in Review
专知会员服务
79+阅读 · 2019年10月10日
热门VIP内容
相关资讯
Ray RLlib: Scalable 降龙十八掌
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
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日
【论文推荐】最新七篇强化学习相关论文—逻辑约束、综述、多任务深度强化学习、参数服务器、事件抽取、分层强化学习、过拟合研究
【论文推荐】最新七篇强化学习相关论文—逻辑约束、综述、多任务深度强化学习、参数服务器、事件抽取、分层强化学习、过拟合研究
专知
25+阅读 · 2018年4月29日
已删除
已删除
将门创投
4+阅读 · 2018年1月19日
R文本分类之RTextTools
R文本分类之RTextTools
R语言中文社区
4+阅读 · 2018年1月17日
分布式TensorFlow入门指南
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】用Python/OpenCV实现增强现实
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
多高的AUC才算高？
多高的AUC才算高？
ResysChina
7+阅读 · 2016年12月7日
相关论文
Servicing Timed Requests on a Line
Arxiv
0+阅读 · 2021年11月30日
Sublinear-time Reductions for Big Data Computing
Arxiv
0+阅读 · 2021年11月30日
Risk-Free Bidding in Complement-Free Combinatorial Auctions
Arxiv
0+阅读 · 2021年11月29日
Bilu-Linial stability, certified algorithms and the Independent Set problem
Arxiv
0+阅读 · 2021年11月29日
Time-optimal self-stabilizing leader election in population protocols
Arxiv
0+阅读 · 2021年11月29日
A Chronology of Set Cover Inapproximability Results
Arxiv
0+阅读 · 2021年11月28日
A note on Matching-Cut in $P_t$-free Graphs
Arxiv
0+阅读 · 2021年11月27日
An Optimal Algorithm for Finding Champions in Tournament Graphs
Arxiv
0+阅读 · 2021年11月26日
Approximate counting and NP search problems
Arxiv
0+阅读 · 2021年11月26日
The Search Problem in Mixture Models
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员
Top