The traveling tournament problem is a well-known benchmark problem of the sports scheduling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive home games and that of consecutive away games are at most two (called TTP(2)). The approximation ratio of the proposed algorithm is 1 + 24/n for n teams, which is the first 1 + O(1/n) approximation algorithm for TTP(2).


翻译:巡回锦标赛问题是体育日程安排的一个众所周知的基准问题。 我们为巡回锦标赛问题提出了一个近似算法,其制约因素包括连续在家游戏的数量和连续离场比赛的数量最多为2个(称为TTP(2) ) 。 拟议算法的近似比率是n队1+ 24/n,这是TP(2) 的第一个1+ O(1/n ) 近似算法。

0
下载
关闭预览

相关内容

专知会员服务
91+阅读 · 2021年6月3日
知识图谱推理,50页ppt,Salesforce首席科学家Richard Socher
专知会员服务
105+阅读 · 2020年6月10日
【普林斯顿大学-微软】加权元学习,Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
【紫冬快讯】自动化所VOT2018实时跟踪竞赛夺冠
中国科学院自动化研究所
3+阅读 · 2018年9月26日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】视频目标分割基础
机器学习研究会
9+阅读 · 2017年9月19日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年10月15日
Ordinal Maximin Share Approximation for Goods
Arxiv
0+阅读 · 2021年10月14日
Arxiv
0+阅读 · 2021年10月13日
VIP会员
Top
微信扫码咨询专知VIP会员