2021/08/19 by Shinji Imahori, Imahori, Shinji · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #Algorithm #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms #Scheduling and Timetabling Solutions #cs.DS
paper · pdf · doi:10.48550/arxiv.2108.08444
6 pages, Appeared in Proceedings of International Symposium on Scheduling 2015, pp.186-191 http://kaede.cs.kobe-u.ac.jp/iss2015/
arxiv created 2021/08/19 · openalex publication_date 2021/08/19 · arxiv updated 2021/08/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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).